Abstract
We present a fully distributed collision avoidance algorithm based on convex optimization for a team of mobile robots. This method addresses the practical case in which agents sense each other via measurements from noisy on-board sensors with no inter-agent communication. Under some mild conditions, we provide guarantees on mutual collision avoidance for a broad class of policies including the one presented. Additionally, we provide numerical examples of computational performance and show that, in both 2D and 3D simulations, all agents avoid each other and reach their desired goals in spite of their uncertainty about the locations of other agents.
This work was supported in part by the Ford-Stanford Alliance program, and by DARPA YFA award D18AP00064. We are grateful for this support.
G. Angeris and K. Shah—These authors contributed equally to this work.
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
Notes
- 1.
The agent performing the specified computation.
- 2.
More specifically, \(v+M=\{v + w \mid w \in M\}\).
- 3.
More generally, a star-shaped domain around \(0 \in R_j(t)\) would suffice.
- 4.
The appendix can be found at https://arxiv.org/abs/1905.12875.
- 5.
References
Agrawal, A., Verschueren, R., Diamond, S., Boyd, S.: A rewriting system for convex optimization problems. J. Control Decis. 5(1), 42–60 (2018)
Augugliaro, F., Schoellig, A.P., D’Andrea, R.: Generation of collision-free trajectories for a quadrocopter fleet: a sequential convex programming approach. In: 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1917–1922, October 2012
Bandyopadhyay, S., Chung, S., Hadaegh, F.Y.: Probabilistic swarm guidance using optimal transport. In: 2014 IEEE Conference on Control Applications (CCA), pp. 498–505, October 2014
van den Berg, J., Guy, S.J., Lin, M., Manocha, D.: Reciprocal n-Body collision avoidance. In: Pradalier, C., Siegwart, R., Hirzinger, G. (eds.) Robotics Research. STAR, vol. 70. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19457-3_1
van den Berg, J., Guy, S., Snape, J., Lin, M., Manocha, D.: Rvo2 library: reciprocal collision avoidance for real-time multi-agent simulation (2016)
van den Berg, J., Lin, M., Manocha, D.: Reciprocal velocity obstacles for real-time multi-agent navigation. In: 2008 IEEE International Conference on Robotics and Automation, pp. 1928–1935. IEEE (2008)
Bertsekas, D., Rhodes, I.: Recursive state estimation for a set-membership description of uncertainty. IEEE Trans. Autom. Control 16(2), 117–128 (1971)
Bezanson, J., Edelman, A., Karpinski, S., Shah, V.B.: Julia: a fresh approach to numerical computing. SIAM Rev. 59(1), 65–98 (2017)
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)
Chen, J., Revels, J.: Robust benchmarking in noisy environments. arXiv preprint arXiv:1608.04295 (2016)
Chen, Y., Cutler, M., How, J.P.: Decoupled multiagent path planning via incremental sequential convex programming. In: 2015 IEEE International Conference on Robotics and Automation (ICRA), pp. 5954–5961 (2015)
Claes, D., Hennes, D., Tuyls, K., Meeussen, W.: Collision avoidance under bounded localization uncertainty. In: 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1192–1198 (Oct 2012)
Domahidi, A., Chu, E., Boyd, S.: ECOS: An SOCP solver for embedded systems. In: 2013 European Control Conference (ECC), pp. 3071–3076. IEEE (2013)
Dunning, I., Huchette, J., Lubin, M.: JuMP: a modeling language for mathematical optimization. SIAM Rev. 59(2), 295–320 (2017)
Gopalakrishnan, B., Singh, A.K., Kaushik, M., Krishna, K.M., Manocha, D.: PRVO: probabilistic reciprocal velocity obstacle for multi robot navigation under uncertainty. In: 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1089–1096, September 2017
Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)
Huang, H., Zhou, Z., Zhang, W., Ding, J., Stipanovic, D.M., Tomlin, C.J.: Safe-reachable area cooperative pursuit. IEEE Trans. Robot. 10(5) (2012)
Janson, L., Schmerling, E., Clark, A., Pavone, M.: Fast marching tree: a fast marching sampling-based method for optimal motion planning in many dimensions. Int. J. Robot. Res. 34(7), 883–921 (2015)
LaValle, S.M., Kuffner, J.J., Jr.: Randomized kinodynamic planning. Int. J. Robot. Res. 20(5), 378–400 (2001)
Liu, Y., Zhao, Y., Wu, F.: Ellipsoidal state-bounding-based set-membership estimation for linear system with unknown-but-bounded disturbances. IET Control Theor. Appl. 10(4), 431–442 (2016)
Ma, X., Jiao, Z., Wang, Z., Panagou, D.: Decentralized prioritized motion planning for multiple autonomous UAVs in 3D polygonal obstacle environments. In: International Conference on Unmanned Aircraft Systems (ICUAS), pp. 292–300 (2016)
Morgan, D., Chung, S.J., Hadaegh, F.Y.: Model predictive control of swarms of spacecraft using sequential convex programming. J. Guidance Control Dyn. 37(6), 1725–1740 (2014)
Preiss, J.A., Hönig, W., Ayanian, N., Sukhatme, G.S.: Downwash-aware trajectory planning for large quadrotor teams. In: 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 250–257, September 2017
Schulman, J., Ho, J., Lee, A.X., Awwal, I., Bradlow, H., Abbeel, P.: Finding locally optimal, collision-free trajectories with sequential convex optimization. In: Robotics: Science and Systems, vol. 9, pp. 1–10. Citeseer (2013)
Şenbaşlar, B., Hönig, W., Ayanian, N.: Robust trajectory execution for multi-robot teams using distributed real-time replanning. In: Correll, N., Schwager, M., Otte, M. (eds.) Distributed Autonomous Robotic Systems. SPAR, vol. 9, pp. 167–181. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-05816-6_12
Shah, K., Schwager, M.: Multi-agent cooperative pursuit-evasion strategies under uncertainty. In: Correll, N., Schwager, M., Otte, M. (eds.) Distributed Autonomous Robotic Systems. SPAR, vol. 9, pp. 451–468. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-05816-6_32
Uteshev, A.Y., Goncharova, M.V.: Point-to-ellipse and point-to-ellipsoid distance equation analysis. J. Comput. Appl. Math. 328, 232–251 (2018)
Wagner, G., Choset, H.: M*: a complete multirobot path planning algorithm with performance bounds. In: 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3260–3267, September 2011
Watson, D.F.: Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. Comput. J. 24(2), 167–172 (1981)
Zhou, D., Wang, Z., Bandyopadhyay, S., Schwager, M.: Fast, on-line collision avoidance for dynamic vehicles using buffered Voronoi cells. IEEE Robot. Autom. Lett. 2(2), 1047–1054 (2017)
Zhu, H., Alonso-Mora, J.: Chance-constrained collision avoidance for MAVs in dynamic environments. IEEE Robot. Autom. Lett. 4(2), 776–783 (2019)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
1 Electronic supplementary material
Below is the link to the electronic supplementary material.
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Angeris, G., Shah, K., Schwager, M. (2022). Fast Reciprocal Collision Avoidance Under Measurement Uncertainty. In: Asfour, T., Yoshida, E., Park, J., Christensen, H., Khatib, O. (eds) Robotics Research. ISRR 2019. Springer Proceedings in Advanced Robotics, vol 20. Springer, Cham. https://doi.org/10.1007/978-3-030-95459-8_12
Download citation
DOI: https://doi.org/10.1007/978-3-030-95459-8_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-95458-1
Online ISBN: 978-3-030-95459-8
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)