Recursive Reductions of Internal Dependencies in Multiagent Planning

Jan Tožička, Jan Jakubův, Antonín Komenda

2016

Abstract

Problems of cooperative multiagent planning in deterministic environments can be efficiently solved both by distributed search or coordination of local plans. In the current coordination approaches, behavior of other agents is modeled as public external projections of their actions. The agent does not require any additional information from the other agents, that is the planning process ignores any dependencies of the projected actions possibly caused by sequences of other agents’ private actions. In this work, we formally define several types of internal dependencies of multiagent planning problems and provide an algorithmic approach how to extract the internally dependent actions during multiagent planning. We show how to take an advantage of the computed dependencies by means of reducing the multiagent planning problems. We experimentally show strong reduction of majority of standard multiagent benchmarks and nearly doubling of solved problems in comparison to a variant of a planner without the reductions. The efficiency of the method is demonstrated by winning in a recent competition of distributed multiagent planners.

Paper Citation

in Harvard Style

Tožička J., Jakubův J. and Komenda A. (2016). Recursive Reductions of Internal Dependencies in Multiagent Planning . In Proceedings of the 8th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART, ISBN 978-989-758-172-4, pages 181-191. DOI: 10.5220/0005754901810191

in Bibtex Style

@conference{icaart16,
author={Jan Tožička and Jan Jakubův and Antonín Komenda},
title={Recursive Reductions of Internal Dependencies in Multiagent Planning},
booktitle={Proceedings of the 8th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,},
year={2016},
pages={181-191},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005754901810191},
isbn={978-989-758-172-4},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 8th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,
TI - Recursive Reductions of Internal Dependencies in Multiagent Planning
SN - 978-989-758-172-4
AU - Tožička J.
AU - Jakubův J.
AU - Komenda A.
PY - 2016
SP - 181
EP - 191
DO - 10.5220/0005754901810191