Kavraki Lab

Consider the problem of coordinating multiple vehicles with kinodynamic constraints that operate in the same environment. The vehicles are able to communicate with a limited range. Their objective is to avoid collisions between them and with the obstacles, while the vehicles move towards their individual goals. An important issue of real-time planning for systems with bounded acceleration is that inevitable collision states (ICS) must also be avoided. The focus of this work is to guarantee safety despite the dynamic constraints with a decentralized motion planning technique that employs only local information. We propose a coordination framework that allows vehicles to generate and select compatible sets of valid trajectories, and prove that this scheme guarantees collision-avoidance in the specified setup. The theoretical results have been also experimentally confirmed with a distributed simulator where each vehicle replans online with a sampling-based, kinodynamic motion planner and uses message-passing to communicate with neighboring agents.

Recent publications describe how to relax some of the requirements for the simulated system. In particular, robots no longer need to have synchronized clocks. Safety is still guaranteed even when the robots communicate at any time during their neighbors’ planning cycle. Our protocol can be easily implemented for any system with dynamics where there is a known strategy for returning to the current state. For example, cars can brake to a halt and remain in the same state, and planes can circle back on their path.

  • Each robot communicates to other nearby robots, but never multi-hop.
  • Robots do not need to know or model the dynamics of their neighbors, but this could improve communication efficiency.
  • A sampling-based planner is used in our simulator, however, there is nothing in the protocol that is specific to this class of planners.

Current research is focusing on removing limitations that preclude a physical implementation. We will show how the theoretical safety guarantees change due to the new system parameters while broadening the class of problem that can be solved with this framework, and continue to experimentally validate our results.

Exploration Videos: 10 vehicles in “random” environment, 5 vehicles in “lab” environment

Navigation Videos: 16 vehicles in the “office” environment, 3 plane-like vehicles in the “geometric” environment