Decentralized probabilistic multi-robot collision avoidance using buffered uncertainty-aware Voronoi cells
Tóm tắt
In this paper, we present a decentralized and communication-free collision avoidance approach for multi-robot systems that accounts for both robot localization and sensing uncertainties. The approach relies on the computation of an uncertainty-aware safe region for each robot to navigate among other robots and static obstacles in the environment, under the assumption of Gaussian-distributed uncertainty. In particular, at each time step, we construct a chance-constrained buffered uncertainty-aware Voronoi cell (B-UAVC) for each robot given a specified collision probability threshold. Probabilistic collision avoidance is achieved by constraining the motion of each robot to be within its corresponding B-UAVC, i.e. the collision probability between the robots and obstacles remains below the specified threshold. The proposed approach is decentralized, communication-free, scalable with the number of robots and robust to robots’ localization and sensing uncertainties. We applied the approach to single-integrator, double-integrator, differential-drive robots, and robots with general nonlinear dynamics. Extensive simulations and experiments with a team of ground vehicles, quadrotors, and heterogeneous robot teams are performed to analyze and validate the proposed approach.
Tài liệu tham khảo
Alonso-Mora, J., Beardsley, P., & Siegwart, R. (2018). Cooperative collision avoidance for nonholonomic robots. IEEE Transactions on Robotics, 34(2), 404–420.
Anderson, T. W., & Bahadur, R. R. (1962). Classification into two multivariate normal distributions with different covariance matrices. The Annals of Mathematical Statistics, 33(2), 420–431.
Andrews, L. C. (1997). Special functions of mathematics for engineers (Vol. 49). SPIE Press.
Arslan, O., & Koditschek, D. E. (2019). Sensor-based reactive navigation in unknown convex sphere worlds. International Journal of Robotics Research, 38(2–3), 196–223.
Astolfi, A. (1999). Exponential stabilization of a wheeled mobile robot via discontinuous control. Journal of Dynamic Systems, Measurement and Control, Transactions of the ASME, 121(1), 121–126.
Axelrod, B., Kaelbling, L. P., & Lozano-Pérez, T. (2018). Provably safe robot navigation with obstacle uncertainty. The International Journal of Robotics Research, 37(13–14), 1760–1774.
Bareiss, D., & van den Berg, J. (2015). Generalized reciprocal collision avoidance. The International Journal of Robotics Research, 34(12), 1501–1514.
Blackmore, L., Ono, M., & Williams, B. C. (2011). Chance-constrained optimal path planning with obstacles. IEEE Transactions on Robotics, 27(6), 1080–1094.
Breitenmoser, A., & Martinoli, A. (2016). On combining multi-robot coverage and reciprocal collision avoidance. Springer tracts in advanced robotics (pp. 49–64). Springer Japan.
Chen, Y., Cutler, M., & How, J.P. (2015). Decoupled multiagent path planning via incremental sequential convex programming. In 2015 IEEE international conference on robotics and automation (ICRA) (pp. 5954–5961). IEEE.
Claes, D., Hennes, D., Tuyls, K., & Meeussen, W. (2012). Collision avoidance under bounded localization uncertainty. In 2012 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 1192–1198). IEEE.
Dawson, C., Jasour, A., Hofmann, A., & Williams, B. (2020). Provably safe trajectory optimization in the presence of uncertain convex obstacles. In 2020 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 6237–6244). IEEE.
Deits, R., Tedrake, R. (2015). Efficient mixed-integer planning for uavs in cluttered environments. In 2015 IEEE international conference on robotics and automation (ICRA) (pp. 42–49). IEEE
Deits, R., & Tedrake, R. (2015). Computing large convex regions of obstacle-free space through semidefinite programming. Springer Tracts in Advanced Robotics, 107, 109–124.
Fiorini, P., & Shiller, Z. (1998). Motion planning in dynamic environments using velocity obstacles. The International Journal of Robotics Research, 17(7), 760–772.
Gopalakrishnan, B., Singh, A.K., Kaushik, M., Krishna, K.M., Manocha, D. (2017). 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). IEEE.
Hardy, J., & Campbell, M. (2013). Contingency planning over probabilistic obstacle predictions for autonomous road vehicles. IEEE Transactions on Robotics, 29(4), 913–929.
Hönig, W., Preiss, J. A., Kumar, T. K., Sukhatme, G. S., & Ayanian, N. (2018). Trajectory planning for quadrotor swarms. IEEE Transactions on Robotics, 34(4), 856–869.
Kamel, M., Alonso-Mora, J., Siegwart, R., Nieto, J. (2017). Robust collision avoidance for multiple micro aerial vehicles using nonlinear model predictive control. In 2017 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 236–243). IEEE.
Kozlov, M. K., Tarasov, S. P., & Khachiyan, L. G. (1980). The polynomial solvability of convex quadratic programming. USSR Computational Mathematics and Mathematical Physics, 20(5), 223–228.
Liu, S., Watterson, M., Mohta, K., Sun, K., Bhattacharya, S., Taylor, C. J., & Kumar, V. (2017). Planning dynamically feasible trajectories for quadrotors using safe flight corridors in 3-d complex environments. IEEE Robotics and Automation Letters, 2(3), 1688–1695.
Luis, C. E., Vukosavljev, M., & Schoellig, A. P. (2020). Online trajectory generation with distributed model predictive control for multi-robot motion planning. IEEE Robotics and Automation Letters, 5(2), 604–611.
Luo, W., Sun, W., & Kapoor, A. (2020). Multi-robot collision avoidance under uncertainty with probabilistic safety barrier certificates. In 2020 advances in neural information processing systems (NeurIPS) (Vol. 33).
Lyons, D., Calliess, J., & Hanebeck, U.D. (2012). Chance constrained model predictive control for multi-agent systems with coupling constraints. In 2012 American control conference (ACC) (pp. 1223–1230). IEEE.
Morgan, D., Subramanian, G. P., Chung, S. J., & Hadaegh, F. Y. (2016). Swarm assignment and trajectory optimization using variable-swarm, distributed auction assignment and sequential convex programming. International Journal of Robotics Research, 35(10), 1261–1285.
Nägeli, T., Meier, L., Domahidi, A., Alonso-Mora, J., & Hilliges, O. (2017). Real-time planning for automated multi-view drone cinematography. ACM Transactions on Graphics, 36(4), 1–10.
Okabe, A., Boots, B., Sugihara, K., & Chiu, S. N. (2009). Spatial tessellations: Concepts and applications of Voronoi diagrams. Wiley.
Pierson, A., Schwarting, W., Karaman, S., & Rus, D. (2020). Weighted buffered voronoi cells for distributed semi-cooperative behavior. In 2020 IEEE international conference on robotics and automation (ICRA) (pp. 5611–5617). IEEE.
Schmerling, E., Pavone, M. (2017). Evaluating trajectory collision probability through adaptive importance sampling for safe motion planning. In Robotics: Science and systems (Vol. 13).
Serra-Gómez, A., Brito, B., Zhu, H., Chung, J.J., Alonso-Mora, J. (2020). With whom to communicate: Learning efficient communication for multi-robot collision avoidance. In 2020 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 11770–11776). IEEE.
Shim, D., Kim, H., & Sastry, S. (2003). Decentralized nonlinear model predictive control of multiple flying robots. In 2003 IEEE conference on decision and control (CDC) (pp. 3621–3626). IEEE.
Tordesillas, J., Lopez, B.T., & How, J.P. (2019). Faster: Fast and safe trajectory planner for flights in unknown environments. In 2019 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 1934–1940). IEEE
Van Den Berg, J., Guy, S. J., Lin, M., & Manocha, D. (2011). Reciprocal n-body collision avoidance. Springer Tracts in Advanced Robotics, 70, 3–19.
Van den Berg, J., Lin, M., & Manocha, D. (2008). Reciprocal velocity obstacles for real-time multi-agent navigation. In 2008 IEEE international conference on robotics and automation (ICRA) (pp. 1928–1935). IEEE.
Wang, M., & Schwager, M. (2019) Distributed collision avoidance of multiple robots with probabilistic buffered voronoi cells. In 2019 international symposium on multi-robot and multi-agent systems (MRS) (pp. 169–175). IEEE.
Zanelli, A., Domahidi, A., Jerez, J., & Morari, M. (2020). FORCES NLP: An efficient implementation of interior-point methods for multistage nonlinear nonconvex programs. International Journal of Control, 1, 13–29.
Zhou, L., Tzoumas, V., Pappas, G. J., & Tokekar, P. (2018). Resilient active target tracking with multiple robots. IEEE Robotics and Automation Letters, 4(1), 129–136.
Zhou, D., Wang, Z., Bandyopadhyay, S., & Schwager, M. (2017). Fast, on-line collision avoidance for dynamic vehicles using buffered Voronoi cells. IEEE Robotics and Automation Letters, 2(2), 1047–1054.
Zhu, H., & Alonso-Mora, J. (2019). B-uavc: Buffered uncertainty-aware Voronoi cells for probabilistic multi-robot collision avoidance. In 2019 international symposium on multi-robot and multi-agent systems (MRS) (pp. 162–168). IEEE.
Zhu, H., Juhl, J., Ferranti, L., Alonso-Mora, J. (2019). Distributed multi-robot formation splitting and merging in dynamic environments. In 2019 international conference on robotics and automation (ICRA) (pp. 9080–9086). IEEE.
Zhu, H., & Alonso-Mora, J. (2019). Chance-constrained collision avoidance for MAVs in dynamic environments. IEEE Robotics and Automation Letters, 4(2), 776–783.