Intelligent Agents (IAᴳ)

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.

Proceedings paper

Department of Applied Mathematics

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.

Proceedings paper

Department of Applied Mathematics

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.