A general formal framework for pathfinding problems with multiple agents

Erdem, Esra and Kısa, Doğa Gizem and Öztok, Umut and Schüller, Peter (2013) A general formal framework for pathfinding problems with multiple agents. In: Twenty-Seventh AAAI Conference on Artificial Intelligence, Bellevue, Washington, USA

Full text not available from this repository. (Request a copy)


Pathfinding for a single agent is the problem of planning a route from an initial location to a goal location in an environment, going around obstacles. Pathfinding for multiple agents also aims to plan such routes for each agent, subject to different constraints, such as restrictions on the length of each path or on the total length of paths, no self-intersecting paths, no intersection of paths/plans, no crossing/meeting each other. It also has variations for finding optimal solutions, e.g., with respect to the maximum path length, or the sum of plan lengths. These problems are important for many real-life applications, such as motion planning, vehicle routing, environmental monitoring, patrolling, computer games. Motivated by such applications, we introduce a formal framework that is general enough to address all these problems: we use the expressive high-level representation formalism and efficient solvers of the declarative programming paradigm Answer Set Programming. We also introduce heuristics to improve the computational efficiency and/or solution quality. We show the applicability and usefulness of our framework by experiments, with randomly generated problem instances on a grid, on a real-world road network, and on a real computer game terrain.
Item Type: Papers in Conference Proceedings
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Esra Erdem
Date Deposited: 20 Jan 2014 15:20
Last Modified: 26 Apr 2022 09:13
URI: https://research.sabanciuniv.edu/id/eprint/23356

Actions (login required)

View Item
View Item