Intelligent Agents (IAᴳ)

In the Intelligent Agents group, we explore various areas of symbolic artificial intelligence with a special regard on intelligent decision making in single and multi-agent scenarios. In all developed concepts, our main aim is to provide important theoretical guarantees, including completeness of algorithms, time/space complexity and reasoning proofs.

More about us

What we do

We are interested in a wide range of topics, including core symbolic search algorithms for multi-agent path finding (MAPF) and its generalizations towards real-life applications, automated planning for robotic agents, multi-robot planning with a focus on coordination, motion planning and related problem solving in robotics, using logical reasoning such as propositional satisfiability (SAT), first-order logic, satisfiability modulo theories (SMT) and constraint satisfaction (CSP).


Ozobot evo

We have a group of small mobile Ozobot evo robots that we use to test path-finding algorithms.


Intelligent Algorithms for Generalized Variants of Multi-Agent Path Finding

Standard projects
Czech Science Foundation
2019 - 2021
Multi-agent path finding (MAPF) is a task of finding non-colliding paths for multiple distinguishable agents in a graph. The MAPF problem represents an important theoretical challenge but also has many practical applications. Solving techniques for the standard MAPF experienced a significant progress recently for both the optimal and the sub-optimal case. This project reflects the growing interest of research community in generalizations of MAPF. Our research aims on study of intelligent solving algorithms in several diverse conceptual directions of MAPF generalizations that are unique to this project. Generalizations in logic formulations of MAPF with focus on expressing MAPF in the SAT modulo theory framework (SMT) and complex local and global constraints are studied. In adversarial variants of MAPF (AMAPF), where multiple teams of agents compete in reaching their goals, the project aims on combination of game-theoretic approach with machine learning. Worthwhile generalizations concern polynomial-time algorithms for MAPF where extensions from undirected to directed graphs are studied.


Unifying Search-Based and Compilation-Based Approaches to Multi-Agent Path Finding through Satisfiability Modulo Theories

Proceedings of the Twelfth International Symposium on Combinatorial Search. Palo Alto, California: Association for the Advancement of Artificial Intelligence (AAAI), 2019. p. 202-203. 1. vol. 1. ISBN 978-1-57735-808-4.
Proceedings paper
We unify search-based and compilation-based approaches to multi-agent path finding (MAPF) through satisfiability modulo theories(SMT). The task in MAPF is to navigate agents in an undirected graph to given goal vertices so that they do not collide. We rephrase Conflict-Based Search (CBS) in the terms of SMT. This idea combines MDD-SAT, a SAT-based optimal MAPF solver, at the low level with conflict elimination of CBS at the high level.

Multi-Agent Path Finding for Large Agents

Li, J.; Surynek, P.; Felner, A.; Ma, H.; Kumar, S.; Koenig, S.
Proceedings of the Twelfth International Symposium on Combinatorial Search. Palo Alto, California: Association for the Advancement of Artificial Intelligence (AAAI), 2019. p. 186-187. 1. vol. 1. ISBN 978-1-57735-808-4.
Proceedings paper
Multi-Agent Path Finding (MAPF) has been widely studied in the AI community. For example, Conflict-Based Search(CBS) is a state-of-the-art MAPF algorithm based on a two-level tree-search. However, previous MAPF algorithms assume that an agent occupies only a single location at any given time, e.g., a single cell in a grid. This limits their applicability in many real-world domains that have geometric agents in lieu of point agents. In this paper, we formalize and study MAPF for large agents that considers the shapesof agents. We present a generalized version of CBS, called Multi-Constraint CBS (MC-CBS), that adds multiple constraints (instead of one constraint) for an agent when it generates a high-level search node. Experimental results show thatall MC-CBS variants significantly outperform CBS. The best variant also outperforms EPEA* (a state-of-the-art A*-based MAPF solver) in all cases and MDD-SAT (a state-of-the-art reduction-based MAPF solver) in some cases.

All publications

Solving Multi-agent Path Finding on Strongly Biconnected Digraphs

Botea, A.; Bonusi, D.; Surynek, P.
Journal of Artificial Intelligence Research. 2018, 62(1), 273-314. ISSN 1076-9757.
Much of the literature on suboptimal, polynomial-time algorithms for multi-agent path finding focuses on undirected graphs, where motion is permitted in both directions along a graph edge. Despite this, traveling on directed graphs is relevant in navigation domains, such as path finding in games, and asymmetric communication networks.

Contact person

prof. RNDr. Pavel Surynek, Ph.D.

Where to find us

Intelligent agents Research Group
Department of Applied Mathematics
Faculty of Information Technology
Czech Technical University in Prague

Room TH:A-1433 (Building A, 14th floor)
Thákurova 7
Prague 6 – Dejvice
160 00

The person responsible for the content of this page: doc. Ing. Štěpán Starosta, Ph.D.