Network-Guided Multi-Robot Path Planning

This project focuses on an interesting variant of path coordination problems, where a static wireless network is responsible for the high-level path planning of multiple robots. In this setup, the robots can divert their computation to tasks such as local obstacle avoidance and localization. This is beneficial in cases where robots are resource constrained and have a limited time to compute a path, such as planetary exploration or warehouse management . Moreover, the network may compute better quality paths for the robots because it has access to more information. Similarly, static nodes can often take advantage of wired communication for coordination, which is more reliable compared to wireless communication. This could be the case in future cyber-physical systems for transportation, which can employ a networked infrastructure to guide automobiles in an urban environment to control traffic.

Distributing the operation of coupled planners over a sensor network is not realistic, because they require the collection of global information from all the network nodes. Moreover, their computational cost becomes quickly prohibitive even for just 6 agents, (in our experiments, more than 4 hours). While existing work has shown how to optimally decouple multi-robot problems into sequential plans of smaller composite robots many problem cannot be decoupled to smaller ones. In the scenarios studied in this work, it is very often the case that within the vicinity of a sensor node there are more than 6 agents whose paths cannot be decoupled. Thus, this work focuses on decoupled solutions. Nevertheless, simple prioritized schemes are not a solution either and often result in deadlocks. Thus, it is necessary to consider more sophisticated decoupled planners, where coordination arises naturally from the constraints imposed on the robots, provides collision avoidance and minimizes the occurrence of deadlocks.

The proposed approach is an online, distributed solution for network-guided, multi-robot path planning where no priorities are used and the sensors have only local information. The sensors first compute alternative local paths for robots in their vicinity and then coordinate to find an assignment of paths to robots. This is achieved through a Distributed Constraint Optimization (DCO) formulation. Coordination Graphs have been used to describe the interaction of agents in DCO, which lead to message-passing solutions. The technique also provides collision avoidance guarantees. Experimental results confirm that the proposed approach achieves collision-free multi-robot path planning for instances where the coupled solution is infeasible and the prioritized schemes quickly results in deadlocks.

This is a novel approach to the problem, since network-based navigation focuses on a single agent and does not consider future interactions of multiple agents. Similarly, multi-robot path planning does not consider network-related constraints. In contrast to prioritized schemes, the DCO formulation allows the assignment of paths to robots that are locally suboptimal but which allow the global existence of a solution to other robots. The algorithm also lends itself to a message-passing protocol, which is appropriate for a network-based problem.

So far, we have studied an abstract version of the problem on a discrete representation, without parameters such as robot dynamics, bandwidth limitations and localization errors. This has allowed us to focus on path planning, to compare against optimal single-agent paths and formulate the requirements for collision avoidance.

The following video, submitted to IROS 2010, summarizes the current contribution.


Related Publications


Acknowledgements

This work has been supported by NSF CNS 0932423. Any opinions and findings expressed in this paper are those of the authors and do not necessarily reflect the views of the sponsor.

People Involved