Abstract
We consider the problem of decentralized multi-robot kinodynamic motion planning in dynamic workspaces. The proposed approach leverages offline precomputation on an invariant planning representation (invariant geometric tree) for low latency online planning and replanning amidst unpredictably moving dynamic obstacles to generate kinodynamically feasible and collision-free time-parameterized polynomial trajectories. Simulation results with up to 10 robots in dynamic workspaces composed of varying obstacle densities (up to \(30\%\) by volume) and speeds (up to \(2.5\,\mathrm{m/s}\)) suggest the use of the proposed methodology for real-time kinodynamic replanning in dynamic workspaces.
A. Desai and N. Michael—We gratefully acknowledge support from industry.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aoude, G.S., Luders, B.D., Joseph, J.M., Roy, N., How, J.P.: Probabilistically safe motion planning to avoid dynamic obstacles with uncertain motion patterns. Auton. Rob. 35(1), 51–76 (2013)
Dellin, C.M., Srinivasa, S.S.: A unifying formalism for shortest path problems with expensive edge evaluations via lazy best-first search over paths with edge selectors. In: Twenty-Sixth International Conference on Automated Planning and Scheduling (2016)
Desai, A., Collins, M., Michael, N.: Efficient kinodynamic multi-robot replanning in known workspaces. In: 2019 International Conference on Robotics and Automation (ICRA), pp. 1021–1027. IEEE (2019)
Desai, A., Michael, N.: Online planning for quadrotor teams in 3-D workspaces via reachability analysis on invariant geometric trees. In: 2020 International Conference on Robotics and Automation (ICRA). IEEE (2020)
Dobson, A., Bekris, K.E.: Improving sparse roadmap spanners. In: 2013 IEEE International Conference on Robotics and Automation, pp. 4106–4111. IEEE (2013)
Hehn, M., D’Andrea, R.: Quadrocopter trajectory generation and control. IFAC Proc. Vol. 44(1), 1485–1491 (2011)
Liu, S.: Motion planning for micro aerial vehicles (2018)
Otte, M., Frazzoli, E.: RRTx: asymptotically optimal single-query sampling-based motion planning with quick replanning. Int. J. Robot. Res. 35(7), 797–822 (2016)
Phillips, M., Likhachev, M.: SIPP: safe interval path planning for dynamic environments. In: 2011 IEEE International Conference on Robotics and Automation, pp. 5628–5635. IEEE (2011)
Silver, D.: Cooperative pathfinding. AIIDE 1, 117–122 (2005)
Turpin, M., Mohta, K., Michael, N., Kumar, V.: Goal assignment and trajectory planning for large teams of interchangeable robots. Auton. Robot. 37(4), 401–415 (2014). https://doi.org/10.1007/s10514-014-9412-1
Vemula, A., Muelling, K., Oh, J.: Path planning in dynamic environments with adaptive dimensionality. In: Ninth Annual Symposium on Combinatorial Search (2016)
Zhu, H., Alonso-Mora, J.: Chance-constrained collision avoidance for MAVs in dynamic environments. IEEE Robot. Autom. Lett. 4(2), 776–783 (2019)
Zucker, M., Kuffner, J., Branicky, M.: Multipartite RRTs for rapid replanning in dynamic environments. In: Proceedings 2007 IEEE International Conference on Robotics and Automation, pp. 1603–1609. IEEE (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Desai, A., Michael, N. (2022). Decentralized Multi-robot Planning in Dynamic 3D Workspaces. In: Matsuno, F., Azuma, Si., Yamamoto, M. (eds) Distributed Autonomous Robotic Systems. DARS 2021. Springer Proceedings in Advanced Robotics, vol 22. Springer, Cham. https://doi.org/10.1007/978-3-030-92790-5_4
Download citation
DOI: https://doi.org/10.1007/978-3-030-92790-5_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-92789-9
Online ISBN: 978-3-030-92790-5
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)