I spent three and a half years as part of my PhD at the University of Oxford developing methods for teams of robots to collaboratively explore unknown environments having major communication challenges. Even as I write this (7 years later) it remains a fairly open research domain with application to important problems like robotic search and rescue, inspection of hazardous areas, and robotic exploration in general.
Role-Based Exploration
More specifically, my thesis proposed “Role-Based Exploration”, a novel exploration algorithm for multi-robot systems that aims to efficiently gather information obtained by all members of the team in a single location. In Role-Based Exploration, some of the robots in the team explore the environment while others act as mobile relays, ferrying information back and forth within the team. By imposing a team hierarchy, choosing clever locations for robots to meet, and applying some simple rules that allow robots to exchange places within this hierarchy, a robust exploration system emerges that reactively adjusts to communication availability and to the shape of the environment.
Key details are in my thesis and several papers published during and shortly after my PhD, but I’ll also provide a few highlights and very basic outline of the approach below. Please note that some of the text and figures below are copied directly from my thesis and papers.
Roles and Hierarchy
First of all, each member of the robot team may act as either (i) an Explorer, or (ii) a Relay. Explorers have the task of exploring unknown areas of the environment, while relays have the task of ferrying information back and forth between explorers and a central location (e.g. the BaseStation, from which the robots are deployed).
A possible hierarchy for Role-Based Exploration. The BaseStation (top) is the root of the hierarchy tree, Explorers (blue) are leaves, and there may be one or more Relays (red) in a branch.
Meeting Up (“Rendezvous”)
As the exploration effort unfolds, Explorers venture deeper and deeper into the environment. Periodically they return to agreed-upon meeting locations (“rendezvous points”) with their parent Relays to provided updated information that the Relay can then pass further up the hierarchy. During that meeting, the subsequent rendezvous point (and the time of the next rendezvous) is also agreed upon. The Relay goes back to its parent, while the Explorer returns to exploring … until the next rendezvous, and so on.
Unknown space is blue, explored space is white. An Explorer (magenta triangle) starts exploring, and its parent Relay (red triangle) follows.
Explorer and Relay are in communication range of one another, but the Relay reaches the edge of the BaseStation’s communication range. It continues following the Explorer for a short time. Soon it decides to turn around and return to BaseStation. At this point the most forward point of progress (the Explorer’s location, shown in subsequent figures as a green circle) is chosen as the next rendezvous point.
The Relay brings new information to the BaseStation, the Explorer continues exploring.
The Explorer can determine exactly when it must turn around in order for it to reach rendezvous at the same time as the Relay. When it turns, it chooses its current location as the next rendezvous point (shown in subsequent figure as a dark green circle).
Relay and Explorer meet at the first rendezvous point. The Explorer communicates its updated map to the Relay, and tells it where the next rendezvous (dark green circle) will be.
More details of the approach are published in one of my first ever papers, Role Based Autonomous Multi-Robot Exploration (co-authors Stephen Cameron and Arnoud Visser).
Choosing Rendezvous Locations
As the research unfolded, it soon became clear that some rendezvous points were very well suited while others were not. Good rendezvous points are in open areas or at junctions, while bad rendezvous points are in corners, deep in enclosed spaces, behind doors, etc.
To choose better rendezvous points, a medial axis transform of the known space was used to calculate the “skeleton” of known space (also known as “thinning”) — specifically Hilditch’s algorithm was used. Together with a few additional steps (e.g. pruning when there were too many points close to one another, and filling when there weren’t enough), this led to a very clean, practical set of potential rendezvous points to choose from.
A partially explored environment: walls are black, unexplored space is blue, explored (free) space is white. Thinning on the free space allows for calculation of the “skeleton” (red lines) and possible rendezvous points (green dots). By choosing the best rendezvous points, robots can meet to exchange information more efficiently, and can replan to meet at another rendezvous point if one of them encounters unexpected obstacles.
This part of the work is described in more detail in our paper Selection of Rendezvous Points for Multi-Robot Exploration in Dynamic Environments.
Dynamic Team Hierarchies
Another issue that arose throughout simulations and trials was that in certain types of environments, it was not ideal to have a static, fixed hierarchy. A couple of examples are shown below.
Two examples scenarios where it would be preferable for the robots to swap roles (i.e., for the explorer to become a relay and for the relay to become an explorer). F1 and F2 indicate unexplored frontiers.
In these situations, it made more sense to have relays and explorers swap roles, and positions in the hierarchy. This was achieved using a single, simple “role swap rule” — described both in the thesis and in our paper Dynamic Team Hierarchies in Communication-Limited Multi-Robot Exploration.
In short, the role swap means that two robots analyse the length of the path to each of their current goals and check whether it would be faster if they switched roles. The longest path among the four paths computed is always eliminated. If a role swap occurs within a single branch of the team hierarchy, this means that new information will travel faster from Explorers to the BaseStation. If it occurs across two separate branches, the role swap generally has a sort of load balancing effect within the team.
In fact, using just this one, simple rule led to some very useful emergent behaviour: many short chains of robots can behave much like one long chain of robots. In certain types of environments, this is a very useful outcome.
A more detailed demonstration of the role swap rule is provided in the figure below. For a detailed description, please see pages 72-73 of my PhD thesis.
Implementation and Comparison to Other Methods
Of course, we compared the approach to several baseline methods in great detail, both in simulation and on real robot teams. Compared to greedy methods (which seek to explore as much unknown space as quickly as possible) the exploration is slower. Compared to leader-follower methods (where the team remains full connected) there was less mutual awareness and more delay in getting new information to the BaseStation. However, Role-Based Exploration (especially with dynamic hierarchies) provided a valuable trade-off between these two: allowing the exploration effort to proceed continuously (and to fully explore the environment), while still receiving periodic updates at the BaseStation, and still maintaining a good degree of control over all robots in the team.
Below are a few fun photos and a screenshot of the implementation on a team of real Pioneer P3AT robots at the University of Seville in Spain. I am deeply indebted to Adrian Jimenez-Gonzalez, Anibal Ollero, and Jose Ramirez Martinez de-Dios for making their laboratory and robots available, and especially to Adrian for assisting with setup and experiments.
Relevant Publications
Links to come.
