Reduced Time-Expansion Graphs and Goal Decomposition for Solving Cooperative Path Finding Sub-Optimally
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.
Cite
Text
Surynek. "Reduced Time-Expansion Graphs and Goal Decomposition for Solving Cooperative Path Finding Sub-Optimally." International Joint Conference on Artificial Intelligence, 2015.Markdown
[Surynek. "Reduced Time-Expansion Graphs and Goal Decomposition for Solving Cooperative Path Finding Sub-Optimally." International Joint Conference on Artificial Intelligence, 2015.](https://mlanthology.org/ijcai/2015/surynek2015ijcai-reduced/)BibTeX
@inproceedings{surynek2015ijcai-reduced,
title = {{Reduced Time-Expansion Graphs and Goal Decomposition for Solving Cooperative Path Finding Sub-Optimally}},
author = {Surynek, Pavel},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2015},
pages = {1916-1922},
url = {https://mlanthology.org/ijcai/2015/surynek2015ijcai-reduced/}
}