Distributed Exploration and Mapping

Exploration is carried out in a distributed fashion using the free market architecture as a coordination mechanism between robots. The robots are able to negotiate and freely exchange tasks for revenue in order to obtain individually profitable tours. By using the negotiation process to continually improve their tours, the tendency is for the robots to cover the environment quickly while remaining far enough apart that there is little repeated coverage. Using multiple robots gives a faster (robots can act in parallel), more robust (no single point of failure) solution.

Cost Model: Costs are currently distance-based. Thus we are trying to minimize travel distance in our exploration.

Revenue Model: Revenue is based on the expected amount of new information to be obtained by visiting a goal point. Currently, the information gained is from the discovery of new occupancy grid values (new terrain).

Distributed negotiations: Negotiations are handled in a completely distributed manner. Robots exchange tasks and revenue with one another without any reliance on a central agent to coordinate the task.

Robustness to communication/robot failure: Communications are always sent to all robots that are reachable. If a robot drops off the network due to moving out of communication range or robot failure, the other robots will simply cease negotiating with that robot until it is redetected.

Exploration algorithm outline: The following is a very general outline of the negotiation protocol that is undergone for the exploration task.

1. robot finds a list of "interesting" goal points (goal points in regions of unknown terrain - some possible goal point selection strategies are described below)
2. the robot greedily arranges all of the goal points into a tour
3. the robot announces an auction for each goal point in its tour - other robots will bid on these tasks by calculating their expected profits from adding this goal to their own tours
4. if another robot bid more money than the auctioneer expected to earn by performing this task, the highest bidder is awarded the task in exchange for the price of the bid
5. once all tasks have been offered, the robot will begin its tour by visiting its first goal point
6. upon arrival at a each goal point, the robot will go to step 1

The negotiation/communications are completely asynchronous, thus a robot may receive calls for bids or other messages in any state (e.g. while on tour, while offering its own tasks for bids, etc...) and thus tours are continuously being updated/improved

Goal point selection strategies: The following is a list of possible goal selection strategies that have been implemented. They are intended to be relatively simple by nature, with the expectation that the negotiation protocol will smooth out the inefficiencies inherent in such methods.

1. Random. The goal points are generated at random places.
2. Greedy. The goal generated is the closest unexplored region to the robot.
3. Uniform grid coverage. Goals are arranged in a grid, equally spaced. The goals can be placed at approximately one sensor radius apart to ensure complete coverage of the environment.
4. Quadtree space decomposition. The goals are generated at the centres of quadtree leaves, which are further subdivided if the fraction of cells within a leaf are that are known/unknown fall below a certain threshold.

Information sharing: Information is shared between the robots in a number of ways.

1. Through negotiation
   • bidder can inform auctioneer if an area being offered is already mapped, and the auctioneer will in turn cancel the auction
   • robots tend to be spaced apart
   • if a goal falls into a region being covered by a different robot, that robot should have the lowest costs to visit that goal, and thus should win an auction for the goal
2. Explicit
   • robots periodically share sections of their maps

Preliminary results: The system has been tested in three different settings.

1. The FRC highbay - a nominally large open space, but cluttered with robots and other equipment.
2. Outdoor patio - an open outdoor area interspersed with tables and chairs.
3. Hotel demo - a demo room in a hotel containing tables, chairs, and over 100 people.

All of these test areas were several hundred square metres in size. Some results from the tests are shown below.

FRC Highbay	Highbay Map 1 Highbay Map 2 Highbay Map 3 Final map
Outer FRC Area	Final Outdoor Map
Nashville Demo	Map 1 of Meeting Facility Map 2 of Meeting Facility Map 3 of Meeting Facility Map 4 of Meeting Facility Floor Plan of Meeting Facility*

Future directions: further testing will be performed, and results showing exploration efficiency (area explored/distance traveled, comparison of goal point selection strategies, etc...) will be posted