---
title: "The Increasing Cost Tree Search for Optimal Multi-Agent Pathfinding"
authors:
  - "Guni Sharon"
  - "Roni Stern"
  - "Mark Goldenberg"
  - "Ariel Felner"
doi: "10.5591/978-1-57735-516-8/IJCAI11-117"
url: "https://ijcai.org/proceedings/2011/117"
pdf: "https://ijcai.org/proceedings/2011/0117.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "662-666"
track: ""
keywords:
---

# The Increasing Cost Tree Search for Optimal Multi-Agent Pathfinding

Guni Sharon, Roni Stern, Mark Goldenberg, Ariel Felner

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 662-666. DOI: [10.5591/978-1-57735-516-8/IJCAI11-117](https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-117)

## Abstract

We address the problem of optimal path finding for multiple agents where agents must not collide and their total travel cost should be minimized. Previous work used traditional single-agent search variants of the A* algorithm. We present a novel formalization for this problem which includes a search tree called the increasing cost tree (ICT) and a corresponding search algorithm that finds optimal solutions. We analyze this new formalization and compare it to the previous state-of-the-art A*-based approach. Experimental results on various domains show the benefits and drawbacks of this approach. A speedup of up to 3 orders of magnitude was obtained in a number of cases.