Sage Journals: Discover world-class research

Abstract

In this overview paper, we present the work of the Goal-Oriented Long-Lived Systems Lab on multi-robot systems. We address multi-robot systems from a decision-making under uncertainty perspective, proposing approaches that explicitly reason about the inherent uncertainty of action execution, and how such stochasticity affects multi-robot coordination. To develop effective decision-making approaches, we take a special focus on (i) temporal uncertainty, in particular of action execution; (ii) the ability to provide rich guarantees of performance, both at a local (robot) level and at a global (team) level; and (iii) scaling up to systems with real-world impact. We summarise several pieces of work and highlight how they address the challenges above, and also hint at future research directions.

Keywords

Multi-robot systems decision-making under uncertainty Markov models formal methods asynchronous execution

Get full access to this article

View all access options for this article.

References

Amir,

Sharon and

Stern, Multi-agent pathfinding as a combinatorial auction, in: Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI), Palo Alto, California, 2015.

Azevedo,

Lacerda,

Hawes and

Lima, Long-run multi-robot planning under uncertain action durations for persistent tasks, in: Proceedings of the 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2020.

F.S.

Barbosa,

Lacerda,

Duckworth,

Tumova and

Hawes, Risk-aware motion planning in partially known environments, in: Proceedings of the 2021 IEEE Conference on Decision and Control (CDC), 2021.

Boutilier, Planning, learning and coordination in multiagent decision processes, in: Proceedings of the 6th Conference on Theoretical Aspects of Rationality and Knowledge (TARK), 1996.

Budd,

Lacerda,

Duckworth,

West,

Lennox and

Hawes, Markov decision processes with unknown state feature values for safe exploration using Gaussian processes, in: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2020.

Costen,

Rigter,

Lacerda and

Hawes, Shared autonomy systems with stochastic operator models, in: Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), 2022.

Das,

Cielniak,

From and

Hanheide, Discrete event simulations for scalability analysis of robotic in-field logistics in agriculture – a case study, in: Proceedings of the IEEE International Conference on Robotics and Automation, Workshop on Robotic Vision and Action in Agriculture (WRVAA), 2018.

De Nijs,

Walraven,

De Weerdt and

Spaan, Constrained multiagent Markov decision processes: A taxonomy of problems and algorithms, Journal of Artificial Intelligence Research70 (2021), 955–1001. doi:10.1613/jair.1.12233.

Duckworth,

Lacerda and

Hawes, Time-bounded mission planning in time-varying domains with semi-MDPs and Gaussian processes, in: Proceedings of the 2020 Conference on Robot Learning (CoRL), 2020.

10.

Eisentraut,

Hermanns,

J.-P.

Katoen and

Zhang, A semantics for every GSPN, in: Proceedings of the 34th International Conference on Applications and Theory of Petri Nets and Concurrency (Petri Nets), Springer, 2013.

11.

Faruq,

Lacerda,

Hawes and

Parker, Simultaneous task allocation and planning under uncertainty, in: Proceedings of the 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Madrid, Spain, 2018.

12.

Foerster,

I.A.

Assael,

De Freitas and

Whiteson, Learning to communicate with deep multi-agent reinforcement learning, in: Proceedings of Advances in Neural Information Processing Systems (NeurIPS), Vol. 29, 2016.

13.

Gautier,

Stephens,

Lacerda,

Hawes and

Wooldridge, Negotiated path planning for non-cooperative multi-robot systems, in: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2022.

14.

Guck,

Hatefi,

Hermanns,

J.-P.

Katoen and

Timmer, Analysis of timed and long-run objectives for Markov automata, Logical Methods in Computer Science10(3) (2014). doi:10.2168/LMCS-10(3:17)2014.

15.

Hatefi and

Hermanns, Model checking algorithms for Markov automata, Electronic Communications of the EASST53 (2012).

16.

M.W.

Khan,

G.P.

Das,

Hanheide and

Cielniak, Incorporating spatial constraints into a Bayesian tracking framework for improved localisation in agricultural environments, in: Proceedings of the 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), IEEE, 2020, pp. 2440–2445.

17.

G.A.

Korsah,

Stentz and

M.B.

Dias, A comprehensive taxonomy for multi-robot task allocation, The International Journal of Robotics Research32(12) (2013), 1495–1512. doi:10.1177/0278364913496484.

18.

Kwiatkowska,

Norman and

Parker, Stochastic model checking, in: Proceedings of the International School on Formal Methods for the Design of Computer, Communication and Software Systems: Performance Evaluation (SFM), Springer, 2007, pp. 220–270.

19.

Lacerda,

Parker and

Hawes, Optimal and dynamic planning for Markov decision processes with co-safe LTL specifications, in: Proceedings of the 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Chicago, IL, USA, 2014.

20.

M.G.

Lagoudakis,

Berhault,

Koenig,

Keskinocak and

A.J.

Kleywegt, Simple auctions with performance guarantees for multi-robot task allocation, in: Proceedings of the 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2004, pp. 698–705.

21.

Mansouri,

Lacerda,

Hawes and

Pecora, Multi-robot planning under uncertain travel times and safety constraints, in: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), Macau, China, 2019.

22.

J.V.

Messias,

M.T.J.

Spaan and

P.U.

Lima, GSMDPs for multi-robot sequential decision-making, in: Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI), 2013.

23.

Oliehoek,

Witwicki and

Kaelbling, Influence-based abstraction for multiagent systems, in: Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI), 2012.

24.

F.A.

Oliehoek and

Amato, A Concise Introduction to Decentralized POMDPs, Springer, 2016.

25.

M.L.

Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley & Sons, Inc., 1994.

26.

Rigter,

Duckworth,

Lacerda and

Hawes, Planning for risk-aversion and expected value in MDPs, in: Proceedings of the 32nd International Conference on Automated Planning and Scheduling (ICAPS), 2022.

27.

Rigter,

Lacerda and

Hawes, A framework for learning from demonstration with minimal human effort, Robotics and Automation Letters (RA-L)5(2) (2020).

28.

Rigter,

Lacerda and

Hawes, Minimax regret optimisation for robust planning in uncertain Markov decision processes, in: Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021.

29.

Rigter,

Lacerda and

Hawes, Risk-averse Bayes-adaptive reinforcement learning, in: Proceedings of Advances in Neural Information Processing Systems (NeurIPS), Vol. 34, 2021.

30.

Silver, Cooperative pathfinding, in: Proceedings of the First AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), AAAI Press, 2005, pp. 117–122.

31.

Stern,

N.R.

Sturtevant,

Felner,

Koenig,

Ma,

T.T.

Walker,

Li,

Atzmon,

Cohen,

T.K.S.

Kumar,

Boyarski and

Bartak, Multi-agent pathfinding: Definitions, variants, and benchmarks, in: Proceedings of the 12th International Symposium on Combinatorial Search (SoCS), 2019, pp. 151–158.

32.

Street,

Lacerda,

Mühlig and

Hawes, Multi-robot planning under uncertainty with congestion-aware models, in: Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2020.

33.

Street,

Lacerda,

Staniaszek,

Mühlig and

Hawes, Context-aware modelling for multi-robot systems under uncertainty, in: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2022.

34.

Street,

Pütz,

Mühlig,

Hawes and

Lacerda, Congestion-aware policy synthesis for multirobot systems, IEEE Transactions on Robotics38(1) (2022).

35.

Vijay, Auction Theory, Academic Press, 2009.