Lecturer: Bernhard Nebel
Fields: Artificial Intelligence/Planning
Content
When using a decentralized planning approach in a cooperative multi-agent system, you either can make use of explicit coordination, i.e. using communication and negotiation during the planning phase, or you rely on implicit coordination, i.e., completely decentralized planning with runtime coordination. We will study such an implicit coordination regime in the setting of multi-agent pathfinding. In this setting it is usually assumed that planning is performed centrally and that the destinations of the agents are common knowledge. We will drop both assumptions and analyze under which conditions it can be guaranteed that the agents reach their respective destinations using implicitly coordinated plans without communication. Furthermore, we will analyze what the computational costs associated with such a coordination regime are. As it turns out, guarantees can be given assuming that the agents are of a certain type. However, the implied computational costs are quite severe.
Literature
- Thomas Bolander, Thorsten Engesser, Robert Mattmüller and Bernhard Nebel. Better Eager Than Lazy? How Agent Types Impact the Successfulness of Implicit Coordination. In Proceedings of the Sixteenth Conference on Principles of Knowledge Representation and Reasoning (KR18), pp. 445-453. 2018. https://gki.informatik.uni-freiburg.de/papers/bolander-etal-kr18.pdf
- Bernhard Nebel, Thomas Bolander, Thorsten Engesser and Robert Mattmüller. Implicitly Coordinated Multi-Agent Path Finding under Destination Uncertainty: Success Guarantees and Computational Complexity. Journal of Artificial Intelligence Research 64, pp. 497-527. 2019. https://gki.informatik.uni-freiburg.de/papers/nebel:et:al:jair-19.pdf
- Roni Stern, Nathan R. Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne T. Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, T. K. Satish Kumar, Roman Barták, Eli Boyarski: Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks. SOCS 2019: 151-159, https://www.aaai.org/ocs/index.php/SOCS/SOCS19/paper/view/18341/17457
Lecturer
Bernhard Nebel received his first degree in Computer Science (Dipl.-Inform.) from the University of Hamburg in 1980 and his Ph.D. (Dr. rer. nat.) from the University of Saarland in 1989. Between 1982 and 1993 he worked on different AI projects at the University of Hamburg, the Technical University of Berlin, ISI/USC, IBM Germany, and the German Research Center for AI (DFKI). From 1993 to 1996 he held an Associate Professor position (C3) at the University of Ulm. Since 1996 he is Professor at Albert-Ludwigs-Universität Freiburg and head of the research group on Foundations of Artificial Intelligence. His research interest are in knowledge representation and reasoning and AI planning, and how you can apply techniques from these areas in robotics. His achievements range from winning the Robocup competition and building an autonomous football table to solving theoretical problems in the area of planning. His current research interest is mostly in multi-agent pathfinding, contributing to the theoretical foundations in this area and applying it in real-world scenarios such as automating the ground-traffic on airports. Bernhard Nebel is an EurAI Fellow and a AAAI Fellow. He is also an elected member of the German Academy of Science Leopoldina and the Academia Europaea. In 2019, he was mentioned as one of the 10 formative researchers of German AI.
Affiliation: Albert-Ludwigs-Universität
Homepage: https://gki.informatik.uni-freiburg.de/~nebel/