Search
Close this search box.

Near-Optimal Multi-Robot Motion Planning with Finite Sampling

Abstract

Near-Optimal Multi-Robot Motion Planning with Finite Sampling
Illustration of the staggered grid in two dimensions. The first layer is denoted by green discs, and the second layer is denoted by red discs. The centers of the discs are the points of the staggered grid

An underlying structure in several sampling-based methods for continuous multi-robot motion planning (MRMP) is the tensor roadmap (TR), which emerges from combining multiple PRM graphs constructed for the individual robots via a tensor product. We study the conditions under which the TR encodes a near-optimal solution for MRMP—satisfying these conditions implies near optimality for a variety of popular planners, including dRRT*, and the discrete methods M* and CBS when applied to the continuous domain.

We develop the first finite-sample analysis of this kind, which specifies the number of samples, their deterministic distribution, and magnitude of the connection radii that should be used by each individual PRM graph, to guarantee near-optimality using the TR.

This significantly improves upon a previous asymptotic analysis, wherein the number of samples tends to infinity. Our new finite sample-size analysis supports guaranteed high-quality solutions in practice within finite time.

To achieve our new result, we first develop a sampling scheme, which we call the staggered grid, for finite-sample motion planning for individual robots, which requires significantly less samples than previous work.  We then extend it to the much more involved MRMP setting which requires to account for interactions among multiple robots. Finally, we report on a few experiments that serve as a  verification of our theoretical findings and raise interesting questions for further investigation.

Links

Contacts

Dror Dayan
Dan Halperin
Kiril Solovey
Marco Pavone
@masterthesis{d-nomrm-21,
  author       = {Dror Dayan},
  title        = {Near-Optimal Multi-Robot Motion Planning with Finite Sampling},
  type         = {{M}.{S}c. Thesis},
  school       = {The Blavatnik School of Computer Science, Tel-Aviv University},
  year         = {2021}
}
@article{dsph-nomrm-23,
  author = {Dror Dayan and Kiril Solovey and Marco Pavone and Dan Halperin},
  journal = {{IEEE} Transactions on Robotics},
  title = {Near-Optimal Multi-Robot Motion Planning with Finite Sampling},
  year = {2023},
  volume = {39},
  number = {5},
  pages = {3422--3436},
  doi = {10.1109/TRO.2023.3281152}
}
@inproccedings{dsph-nomrm-21,
  author = {Dror Dayan and Kiril Solovey and Marco Pavone and Dan Halperin},
  booktitle = {Proceedings of {IEEE} International Conference on Robotics and Automation ({ICRA})}, 
  title = {Near-Optimal Multi-Robot Motion Planning with Finite Sampling}, 
  year = {2021},
  pages = {9190--9196},
  doi = {10.1109/ICRA48506.2021.9561009}
}
@article{dsph-nomrm-20,
  author       = {Dror Dayan and Kiril Solovey and Marco Pavone and Dan Halperin},
  title        = {Near-Optimal Multi-Robot Motion Planning with Finite Sampling},
  journal      = {CoRR},
  volume       = {abs/2011.08944},
  year         = {2020},
  url          = {https://arxiv.org/abs/2011.08944},
  eprinttype   = {arXiv},
  eprint       = {2011.08944},
  timestamp    = {Mon, 19 Dec 2022 22:09:32 +0100},
  biburl       = {https://dblp.org/rec/journals/corr/abs-2011-08944.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

Yair Oz - Webcreator

Contact

Skip to content