---
title: "Reduced Time-Expansion Graphs and Goal Decomposition for Solving Cooperative Path Finding Sub-Optimally"
authors:
  - "Pavel Surynek"
doi: ""
url: "https://ijcai.org/proceedings/2015/272"
pdf: "https://ijcai.org/proceedings/2015/0272.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "1916-1921"
track: "Main Track"
keywords:
---

# Reduced Time-Expansion Graphs and Goal Decomposition for Solving Cooperative Path Finding Sub-Optimally

Pavel Surynek

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 1916-1921.

## Abstract

Solving cooperative path finding (CPF) by translating it to propositional satisfiability represents a viable option in highly constrained situations. The task in CPF is to relocate agents from their initial positions to given goals in a collision free manner. In this paper, we propose a reduced time expansion that is focused on makespan sub-optimal solving. The suggested reduced time expansion is especially beneficial in conjunction with a goal decomposition where agents are relocated one by one.