Below you can find information regarding software packages that our research group has released or can provide upon request:
- Stable Sparse RRT (SST): Efficient Asymptotically Near-Optimal Kinodynamic Motion Planning
- Multi-agent Path Finding: Push and Swap code
- Sparse Representations for Motion Planning: SPARS and SPARS 2 available on OMPL
- PRACSYS software: An Extensible Architecture for Composing Motion Controllers, Motion Planners and Task Planners
We have developed the Stable Sparse-RRT (SST) algorithm, which provides favorable properties for systems where a steering function (BVP solver) may not be available, while being highly efficient. It can be shown that SST is asymptotically near-optimal and with a small modification (SST*) it can also provide asymptotic optimality for kinodynamic problems under some mild assumptions. In addition, SST maintains a sparse data structure, where the number of nodes stored in their trees is significantly lower than RRT providing computational benefits. More details and a link to the codebase can be found under the SST webpage.
Our efforts in the area of Complete and Tractable Multi-Robot Path Planning started in 2011 with an algorithm called Push and Swap, which has polynomial running time and is complete but suboptimal for the multi-agent path finding problem. The algorithm has attracted attention and we received multiple requests for the source code. Since 2011 Ryan Luna has continued working on optimizing this implementation, in collaboration with Athanasios Krontiris and Kostas Bekris.
The group has also worked on showing the relation between such efficient and complete but suboptimal planners and algorithmic contributions on the pebble motion problem. We will soon release the code that provides implementations for multiple variations of these methods.
The available code for Push and Swap above provides sequential solutions, i.e., where only one agent moves at a time. There is also work on a parallel version of Push and Swap. The implementation is not as optimized yet but we can provide it upon request.
Asymptotically Near-Optimal Roadmap-Based Planners SPARS and SPARS2 have been released as part of the Open Motion Planning Library maintained by the Physical and Biological Computing Group at Rice University. The benefit of these methods is that they correspond to sparse motion planning data structures that can be queried and communicated efficiently, while at the same time they are also able to provide guarantees regarding the quality of the resulting paths.
PRACSYS software: An Extensible Architecture for Composing Motion Controllers, Motion Planners and Task Planners
Our research group is working on a common software package that has been utilized for a variety of research projects over the last few years. Our objective is to provide an extensible software architecture so that the integration of low-level motion controllers with motion planners and higher-level task planers is streamlined.
We have since significantly revised and extended the functionality of our software package. Our current main focus is on the definition of proper interfaces for composing motion and task planners. Feel free to contact us if you are interested in the latest version and we will share a Mercurial repository.
Examples of publications that have utilized this software platform include the following:
- Efficient Sampling-Based Motion Planning With Asymptotic Near-Optimality Guarantees For Systems With Dynamics, IROS 2013
- From Feasibility Tests To Path Planners For Multi-Agent Pathfinding, SOCS 2013
- Minimizing Conflicts Between Moving Agents Over A Set Of Non-Homotopic Paths Through Regret Minimization, In AAAI 2013 Workshop on Intelligent Robotic Systems
- Maintaining Team Coherence Under The Velocity Obstacle Framework”, In AAMAS 2012
- Multi-Level Formation Roadmaps For Collision-Free Dynamic Shape Changes With Non-Holonomic Teams, In ICRA 2012
- Using Minimal Communication To Improve Decentralized Conflict Resolution For Non-Holonomic Vehicles, In IROS 2011