The Before,During,and After of Multi-robot Deadlock

Abstract

Collision avoidance for multi-robot systems is a well-studied problem. Recently, control barrier functions (CBFs) have been proposed for synthesizing controllers that guarantee collision avoidance and goal stabilization for multiple robots. However, it has been noted that reactive control synthesis methods (such as CBFs) are prone to deadlock, an equilibrium of system dynamics that causes the robots to stall before reaching their goals. In this paper, we analyze the closed-loop dynamics of robots using CBFs, to characterize controller parameters, initial conditions, and goal locations that invariably lead the system to deadlock. Using tools from duality theory, we derive geometric properties of robot configurations of an N robot system once it is in deadlock and we justify them using the mechanics interpretation of KKT conditions. Our key deductions are that (1) system deadlock is characterized by a force equilibrium on robots and (2) deadlock occurs to ensure safety when safety is at the brink of being violated. These deductions allow us to interpret deadlock as a subset of the state space, and we show that this set is non-empty and located on the boundary of the safe set. By exploiting these properties, we analyze the number of admissible robot configurations in deadlock and develop a provably correct decentralized algorithm for deadlock resolution to safely deliver the robots to their goals. This algorithm is validated in simulations as well as experimentally on Khepera-IV robots For an interactive version of this paper, please visit https://arxiv.org/abs/2206.01781.

Keywords

Collision avoidance optimization and optimal control duality theory

Get full access to this article

View all access options for this article.

References

Alonso-Mora

DeCastro

Raman

, et al. (2018) Reactive mission and motion planning with deadlock resolution avoiding dynamic obstacles. Autonomous Robots 42(4): 801–824.

Ames

Grizzle

, et al. (2017) Control barrier function based quadratic programs for safety critical systems. IEEE Transactions on Automatic Control 62(8): 3861–3876.

Borrmann

Wang

Ames

, et al. (2015) Control barrier certificates for safe swarm behavior. IFAC-PapersOnLine 48(27): 68–73.

Boyd

Vandenberghe

(2004) Convex Optimization. Cambridge university press.

Burgard

Moors

Stachniss

, et al. (2005) Coordinated multi-robot exploration. IEEE Transactions on Robotics 21(3): 376–386.

Cortes

Martinez

Karatas

, et al. (2004) Coverage control for mobile sensing networks. IEEE Transactions on Robotics and Automation 20(2): 243–255.

Douthwaite

(2019) Multi-agent Collision Avoidance Using Interval Analysis and Symbolic Modelling with its Application to the Novel Polycopter. PhD thesis. University of Sheffield.

Douthwaite

Zhao

Mihaylova

(2018) A comparative study of velocity obstacle approaches for multi-agent systems. In: 2018 UKACC 12th International Conference on Control (CONTROL). IEEE, pp. 289–294.

Douthwaite

Zhao

Mihaylova

(2019) Velocity obstacle approaches for multi-agent collision avoidance. Unmanned Systems 07(01): 55–64.

10.

Duhaut

Carrillo

Saint-Aime

(2007) Avoiding deadlock in multi-agent systems. In: 2007 IEEE International Conference on Systems, Man and Cybernetics, pp. 1642–1647.

11.

Feng

(2019) Optimal perimeter guarding with heterogeneous robot teams: complexity analysis and effective algorithms. IEEE Robotics and Automation Letters 5(2): 430–437.

12.

Fiorini

Shiller

(1998) Motion planning in dynamic environments using velocity obstacles. The International Journal of Robotics Research 17(7): 760–772.

13.

Grover

Liu

Sycara

(2019) Deadlock analysis and resolution in multi-robot systems (extended version). https://arxiv.org/abs/1911.09146.

14.

Grover

Liu

Sycara

(2020a) Why does symmetry cause deadlocks? IFAC-PapersOnLine 53(2): 9746–9753.

15.

Grover

Liu

Sycara

(2020b) Parameter identification for multirobot systems using optimization based controllers (extended version). arXiv preprint arXiv:2009.13817.

16.

Hokayem

Stipanović

Spong

(2010) Coordination and collision avoidance for lagrangian systems with disturbances. Applied Mathematics and Computation 217(3): 1085–1094.

17.

Jager

Nebel

(2001) Decentralized collision avoidance, deadlock detection, and deadlock resolution for multiple mobile robots. In: Proceedings 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems. Expanding the Societal Role of Robotics in the the Next Millennium (Cat. No. 01CH37180). IEEE, Vol. 3, pp. 1213–1219.

18.

Kantor

Singh

Peterson

, et al. (2003) Distributed search and rescue with robot and sensor teams. In: Field and Service Robotics. Springer, pp. 529–538.

19.

Leitmann

Skowronski

(1977) Avoidance control. Journal of Optimization Theory and Applications 23(4): 581–591.

20.

Leitmann

Skowronski

(1983) A note on avoidance control. Optimal Control Applications and Methods 4(4): 335–342.

21.

Gupta

Payandeh

(2005) Motion planning of multiple agents in virtual environments using coordination graphs. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation. IEEE, pp. 378–383.

22.

O’Donnell

(1989) Deadlockfree and collision-free coordination of two robot manipulators. In: Proc. IEEE International Conference on Robotics and Automation, pp. 484–489.

23.

Ogren

Egerstedt

Xiaoming Hu

(2002) A control lyapunov function approach to multiagent coordination. IEEE Transactions on Robotics and Automation 18(5): 847–851.

24.

Olfati-Saber

Fax

Murray

(2007) Consensus and cooperation in networked multi-agent systems. Proceedings of the IEEE 95(1): 215–233.

25.

Pan

Verginis

Wells

, et al. (2020) Augmenting control policies with motion planning for robust and safe multi-robot navigation. In: ‘2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, pp. 6975–6981.

26.

Petti

Fraichard

(2005) Safe motion planning in dynamic environments. In: ‘2005 IEEE/RSJ International Conference on Intelligent Robots and Systems’. IEEE, pp. 2210–2215.

27.

Rodríguez-Seda

Stipanović

Spong

(2016) Guaranteed collision avoidance for autonomous systems with acceleration constraints and sensing uncertainties. Journal of Optimization Theory and Applications 168(3): 1014–1038.

28.

Stipanović

Hokayem

Spong

, et al. (2007) Cooperative avoidance control for multiagent systems. Journal of Dynamic Systems, Measurement, and Control 129(5): 699–707.

29.

Van Den Berg

Guy

Lin

, et al. (2011) Reciprocal n-body collision avoidance In: Robotics Research. Springer, pp. 3–19.

30.

Van den Berg

Lin

Manocha

(2008) Reciprocal velocity obstacles for real-time multi-agent navigation In: ‘2008 IEEE International Conference on Robotics and Automation’. IEEE. pp. 1928–1935.

31.

Wang

Ames

Egerstedt

(2017) Safety barrier certificates for collisions-free multirobot systems. IEEE Transactions on Robotics 33(3): 661–674.

32.

Wilkie

Van Den Berg

Manocha

(2009) Generalized velocity obstacles In: ‘2009 IEEE/RSJ International Conference on Intelligent Robots and Systems’. IEEE, pp. 5573–5578.

33.

Yamaguchi

(1999) A cooperative hunting behavior by mobile-robot troops. the International Journal of Robotics Research 18(9): 931–940.

34.

Zhou

Liu

, et al. (2017a) Collision and deadlock avoidance in multirobot systems: A distributed approach. IEEE Transactions on Systems, Man, and Cybernetics: Systems 47(7): 1712–1726.

35.

Zhou

Liu

, et al. (2017b) Collision and deadlock avoidance in multirobot systems: A distributed approach. IEEE Transactions on Systems, Man, and Cybernetics: Systems 47(7): 1712–1726.