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.
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.
Information sharing: Information is shared between the robots in a number of ways.
Preliminary results: The system has been tested in three different settings.
All of these test areas were several hundred square metres in size. Some results from the tests are shown below.
Outer FRC Area
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