Abstract
Robust trajectory execution is an extension of cooperative collision avoidance that takes pre-planned trajectories directly into account. We propose an algorithm for robust trajectory execution that compensates for a variety of dynamic changes, including newly appearing obstacles, robots breaking down, imperfect motion execution, and external disturbances. Robots do not communicate with each other and only sense other robots’ positions and the obstacles around them. At the high-level we use a hybrid planning strategy employing both discrete planning and trajectory optimization with a dynamic receding horizon approach. The discrete planner helps to avoid local minima, adjusts the planning horizon, and provides good initial guesses for the optimization stage. Trajectory optimization uses a quadratic programming formulation, where all safety-critical parts are formulated as hard constraints. At the low-level, we use buffered Voronoi cells as a multi-robot collision avoidance strategy. Compared to ORCA, our approach supports higher-order dynamic limits and avoids deadlocks better. We demonstrate our approach in simulation and on physical robots, showing that it can operate in real time.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Since our approach can accommodate many sensing modalities, we do not provide a specific sensing capability in the general problem.
References
Alonso-Mora, J., Beardsley, P.A., Siegwart, R.: Cooperative collision avoidance for nonholonomic robots. IEEE Trans. Robot. (T-RO) 34(2), 404–420 (2018)
van den Berg, J., Guy, S.J., Lin, M.C., Manocha, D.: Reciprocal n-body collision avoidance. In: International Symposium of Robotic Research (ISRR), pp. 3–19 (2009). http://gamma.cs.unc.edu/RVO2/
van den Berg, J.P., Lin, M.C., Manocha, D.: Reciprocal velocity obstacles for real-time multi-agent navigation. In: IEEE International Conference on Robotics and Automation (ICRA), pp. 1928–1935 (2008)
Cortes, C., Vapnik, V.: Support-vector networks. Mach. Learn. 20(3), 273–297 (1995)
Debord, M., Hönig, W., Ayanian, N.: Trajectory planning for heterogeneous robot teams. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (2018). accepted. To appear
Dresner, K.M., Stone, P.: A multiagent approach to autonomous intersection management. J. Artif. Intell. Res. (JAIR) 31, 591–656 (2008)
Farouki, R.T.: The bernstein polynomial basis: a centennial retrospective. Comput. Aided Geom. Des. 29(6), 379–419 (2012)
Ferreau, H.J., Kirches, C., Potschka, A., Bock, H.G., Diehl, M.: qpOASES: a parametric active-set algorithm for quadratic programming. Math. Program. Comput. 6(4), 327–363 (2014)
Hönig, W., Preiss, J.A., Kumar, T.K.S., Sukhatme, G.S., Ayanian, N.: Trajectory planning for quadrotor swarms. IEEE Trans. Robot. (T-RO) 34(4), 856–869 (2018)
Hornung, A., Wurm, K.M., Bennewitz, M., Stachniss, C., Burgard, W.: OctoMap: An efficient probabilistic 3D mapping framework based on octrees. Auton. Robot. 34(3), 189–206 (2013). http://octomap.github.com
Mattingley, J., Boyd, S.: CVXGEN: a code generator for embedded convex optimization. Optim. Eng. 13(1), 1–27 (2012)
Morris, R., Pasareanu, C.S., Luckow, K.S., Malik, W., Ma, H., Kumar, T.K.S., Koenig, S.: Planning, scheduling and monitoring for airport surface operations. In: AAAI Workshop on Planning for Hybrid Systems. AAAI Workshops, vol. WS-16-12, pp. 608–614 (2016)
Oleynikova, H., Burri, M., Taylor, Z., Nieto, J.I., Siegwart, R., Galceran, E.: Continuous-time trajectory optimization for online UAV replanning. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 5332–5339 (2016)
Richter, C., Bry, A., Roy, N.: Polynomial trajectory planning for aggressive quadrotor flight in dense indoor environments. In: International Symposium of Robotic Research (ISRR), pp. 649–666 (2013)
Stellato, B., Banjac, G., Goulart, P., Bemporad, A., Boyd, S.: OSQP: An operator splitting solver for quadratic programs. ArXiv e-prints, Jan 2018
Usenko, V.C., von Stumberg, L., Pangercic, A., Cremers, D.: Real-time trajectory replanning for MAVs using uniform B-splines and a 3D circular buffer. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 215–222 (2017)
Wang, L., Ames, A.D., Egerstedt, M.: Safety barrier certificates for collisions-free multirobot systems. IEEE Trans. Robot. (T-RO) 33(3), 661–674 (2017)
Wurman, P.R., D’Andrea, R., Mountz, M.: Coordinating hundreds of cooperative, autonomous vehicles in warehouses. AI Mag. 29(1), 9–20 (2008)
Zhou, D., Wang, Z., Bandyopadhyay, S., Schwager, M.: Fast,: On-line collision avoidance for dynamic vehicles using buffered voronoi cells. IEEE Robot. Autom. Lett. (RA-L) 2(2), 1047–1054 (2017)
Acknowledgements
This research was supported in part by Office of Naval Research grant N00014-14-1-073 and National Science Foundation grant 1724399. B. Şenbaşlar gratefully acknowledges the support from the Fulbright program sponsored by U.S. Department of State.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Şenbaşlar, B., Hönig, W., Ayanian, N. (2019). Robust Trajectory Execution for Multi-robot Teams Using Distributed Real-time Replanning. In: Correll, N., Schwager, M., Otte, M. (eds) Distributed Autonomous Robotic Systems. Springer Proceedings in Advanced Robotics, vol 9. Springer, Cham. https://doi.org/10.1007/978-3-030-05816-6_12
Download citation
DOI: https://doi.org/10.1007/978-3-030-05816-6_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-05815-9
Online ISBN: 978-3-030-05816-6
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)