This page contains images and movies related to my research on complex task allocation for multirobot teams. You may want to take a look at my research and publications pages to get some more indepth and technical descriptions of what is going on in the images and movies below.
Most of the results that are on this page come from our autonomous E-Gator platforms, which are John Deere electric utility vehicles that have been converted into robots. We've also run our system on a team of ActivMedia PioneerII-DX indoor robots.
As mentioned above, I've been looking at the problem of complex task allocation for multirobot teams. Essentially, this means that I am looking at problems where the mission can be described in terms of complex tasks that may have multiple solution strategies. The best strategy for a given complex task depends on the state of the world, which robots are going to perform it, and what other tasks these robots plan to perform. We've created a market-based solution in which tasks can be traded at multiple levels of abstraction by trading task trees in the market, which allows the team to decide between both better allocations and better task decompositions in a distributed manner.
The following images and movies come from the example domain of Area Reconnaissance. The team of robots is tasked with a set of Named Areas of Interest (NAI) that must be covered by viewing them with their sensors. In order to view the areas, robots may visit a set of Observations Points (OP). We would also like to restrict the robots from entering the NAIs (unless absolutely necessary), since this is potentially risky. The mission is achieved by the robots visiting a set of OPs that sufficiently cover the NAIs, and we would like the robots to do this as efficiently as possible. This means we would like to minimize either the total distance driven by the robots, or the total time taken by the team.
Example instances of area reconnaissance scenarios are shown in the following images. The first is taken from map data from the E-Gator robots, and the second shows an example in simulation.
The next figure shows an example of an AND/OR task tree for an area reconnaissance problem with three NAI. The solid lines indicate the parent node is an AND-operator (which means all the subtasks must be performed to satisfy this node), and the dashed lines indicate an OR node (at least one of the subtasks must be performed).
The next few images and movies show some examples of robot teams solving area reconnaissance problems using our market-based approach. In each case, an operator introduces complex area coverage tasks and the robots then bid on the associated task tree. While bidding, the robots may determine that they have better plans for some of the abstract tasks: so in addition to bidding on the mission as decomposed by the operator agent, the robots can come up with their own decompositions that they can use if they win those tasks. Once the auction is cleared and the tasks are distributed among the team, the robots can then hold peer-to-peer task tree auctions and improve the overall solution.
In this first example, a team of 6 robots have solved an area reconnaissance problem with 40 named areas of interest. The global objective is to minimize the total travel distance incurred by the team. The first frame shows the allocation after the operator agent's auction. In the subsequent frames, the solution is improved using peer-to-peer auctions between the robots. It is possible to see inefficiencies in the initial allocation improving with each auction. Both the way in which tasks are decomposed and the way in which they are allocated changes to bring about this improvement.
The following movies demonstrate the execution of complex tasks. In each case, tasks are intially auctioned to the team, following which they can trade amongst themselves, improving the solution. The robot concurrently execute their tasks while holding these auctions. At the start of execution, the robots have no prior knowledge about their environment. As they discover obstacles and other terrain features during execution local costs and visibilty changes, and thus the robots may need to reallocate or redecompose some tasks. Redecomposition occurs both when a goal point is determined to be unreachable, or during a periodic check to see if a more efficient plan can be found given the new information.
The first movie shows a simulated environment with 4 robots and 5 named areas of interest. As the robots execute the mission, the new task decompositions and allocations can be seen.
This next set of movies come from a run on 2 of the E-Gators. Here the robots are given a mission with 4 named areas of interest. The first movie is a filmed run of the robots in Schenley Park. The second movie shows the maps built by the robots during execution using their laser scanners (black areas are unknown, dark green areas are free space, and bright green areas are obstacles). Three of the areas are covered by single robots, while the area in the middle has shared coverage between the two robots. As the robots execute the task, it is possible to see changes in task decompositions as obstacles and other terrain features are discovered. In particular, towards the end of the second movie the robot in the lower right discovers some obstacles that increase the cost of its current decomposition, so a different plan with similar coverage and a lower cost is used.