Plan coordination mechanisms and the price of autonomy

J.Renze Steenhuisen, Cees Witteveen, Yingqian Zhang

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

3 Citations (Scopus)

Abstract

Task-based planning problems for multi-agent systems require multiple agents to find a joint plan for a constrained set of tasks. Typically, each agent receives a subset of tasks to complete. Due to task interdependencies, such task allocations induce interdependencies between agents as well. These interdependencies will prevent the agents from making a plan for their subset of tasks independently from each other, since the combination of such autonomously constructed plans will most probably result in conflicting plans. Therefore, a plan-coordination mechanism is needed to guarantee a conflict-free globally feasible plan.

In this paper, we first present a brief overview of the main results achieved on plan coordination for autonomous planning agents, distinguishing between problems associated with deciding whether a coordination mechanism is necessary, designing an arbitrary coordination mechanism, and designing an optimal (minimal) coordination mechanism. After finding out that designing an optimal coordination mechanism is difficult, we concentrate on an algorithm that is able to find a (non-trivial) coordination mechanism that is not always minimal. We then discuss some subclasses of plan-coordination instances where this algorithm performs very badly, but also some class of instances where a nearly optimal coordination mechanism is returned.
Original languageEnglish
Title of host publicationComputational Logic in Multi-Agent Systems
Subtitle of host publication8th International Workshop, CLIMA VIII, Porto, Portugal, September 10-11, 2007. Revised Selected and Invited Papers
EditorsF. Sadri, K. Satoh
Place of PublicationBerlin
PublisherSpringer
Pages1-21
ISBN (Electronic)978-3-540-88833-8
ISBN (Print)978-3-540-88832-1
DOIs
Publication statusPublished - 2008

Publication series

NameLNCS
Volume5056

Fingerprint

Planning
Multi agent systems

Cite this

Steenhuisen, J. R., Witteveen, C., & Zhang, Y. (2008). Plan coordination mechanisms and the price of autonomy. In F. Sadri, & K. Satoh (Eds.), Computational Logic in Multi-Agent Systems: 8th International Workshop, CLIMA VIII, Porto, Portugal, September 10-11, 2007. Revised Selected and Invited Papers (pp. 1-21). (LNCS; Vol. 5056). Berlin: Springer. https://doi.org/10.1007/978-3-540-88833-8_1
Steenhuisen, J.Renze ; Witteveen, Cees ; Zhang, Yingqian. / Plan coordination mechanisms and the price of autonomy. Computational Logic in Multi-Agent Systems: 8th International Workshop, CLIMA VIII, Porto, Portugal, September 10-11, 2007. Revised Selected and Invited Papers. editor / F. Sadri ; K. Satoh. Berlin : Springer, 2008. pp. 1-21 (LNCS).
@inbook{bfffd73138e94fac827bb3c4b1494eca,
title = "Plan coordination mechanisms and the price of autonomy",
abstract = "Task-based planning problems for multi-agent systems require multiple agents to find a joint plan for a constrained set of tasks. Typically, each agent receives a subset of tasks to complete. Due to task interdependencies, such task allocations induce interdependencies between agents as well. These interdependencies will prevent the agents from making a plan for their subset of tasks independently from each other, since the combination of such autonomously constructed plans will most probably result in conflicting plans. Therefore, a plan-coordination mechanism is needed to guarantee a conflict-free globally feasible plan.In this paper, we first present a brief overview of the main results achieved on plan coordination for autonomous planning agents, distinguishing between problems associated with deciding whether a coordination mechanism is necessary, designing an arbitrary coordination mechanism, and designing an optimal (minimal) coordination mechanism. After finding out that designing an optimal coordination mechanism is difficult, we concentrate on an algorithm that is able to find a (non-trivial) coordination mechanism that is not always minimal. We then discuss some subclasses of plan-coordination instances where this algorithm performs very badly, but also some class of instances where a nearly optimal coordination mechanism is returned.",
author = "J.Renze Steenhuisen and Cees Witteveen and Yingqian Zhang",
year = "2008",
doi = "10.1007/978-3-540-88833-8_1",
language = "English",
isbn = "978-3-540-88832-1",
series = "LNCS",
publisher = "Springer",
pages = "1--21",
editor = "Sadri, {F. } and K. Satoh",
booktitle = "Computational Logic in Multi-Agent Systems",
address = "Germany",

}

Steenhuisen, JR, Witteveen, C & Zhang, Y 2008, Plan coordination mechanisms and the price of autonomy. in F Sadri & K Satoh (eds), Computational Logic in Multi-Agent Systems: 8th International Workshop, CLIMA VIII, Porto, Portugal, September 10-11, 2007. Revised Selected and Invited Papers. LNCS, vol. 5056, Springer, Berlin, pp. 1-21. https://doi.org/10.1007/978-3-540-88833-8_1

Plan coordination mechanisms and the price of autonomy. / Steenhuisen, J.Renze; Witteveen, Cees; Zhang, Yingqian.

Computational Logic in Multi-Agent Systems: 8th International Workshop, CLIMA VIII, Porto, Portugal, September 10-11, 2007. Revised Selected and Invited Papers. ed. / F. Sadri; K. Satoh. Berlin : Springer, 2008. p. 1-21 (LNCS; Vol. 5056).

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

TY - CHAP

T1 - Plan coordination mechanisms and the price of autonomy

AU - Steenhuisen, J.Renze

AU - Witteveen, Cees

AU - Zhang, Yingqian

PY - 2008

Y1 - 2008

N2 - Task-based planning problems for multi-agent systems require multiple agents to find a joint plan for a constrained set of tasks. Typically, each agent receives a subset of tasks to complete. Due to task interdependencies, such task allocations induce interdependencies between agents as well. These interdependencies will prevent the agents from making a plan for their subset of tasks independently from each other, since the combination of such autonomously constructed plans will most probably result in conflicting plans. Therefore, a plan-coordination mechanism is needed to guarantee a conflict-free globally feasible plan.In this paper, we first present a brief overview of the main results achieved on plan coordination for autonomous planning agents, distinguishing between problems associated with deciding whether a coordination mechanism is necessary, designing an arbitrary coordination mechanism, and designing an optimal (minimal) coordination mechanism. After finding out that designing an optimal coordination mechanism is difficult, we concentrate on an algorithm that is able to find a (non-trivial) coordination mechanism that is not always minimal. We then discuss some subclasses of plan-coordination instances where this algorithm performs very badly, but also some class of instances where a nearly optimal coordination mechanism is returned.

AB - Task-based planning problems for multi-agent systems require multiple agents to find a joint plan for a constrained set of tasks. Typically, each agent receives a subset of tasks to complete. Due to task interdependencies, such task allocations induce interdependencies between agents as well. These interdependencies will prevent the agents from making a plan for their subset of tasks independently from each other, since the combination of such autonomously constructed plans will most probably result in conflicting plans. Therefore, a plan-coordination mechanism is needed to guarantee a conflict-free globally feasible plan.In this paper, we first present a brief overview of the main results achieved on plan coordination for autonomous planning agents, distinguishing between problems associated with deciding whether a coordination mechanism is necessary, designing an arbitrary coordination mechanism, and designing an optimal (minimal) coordination mechanism. After finding out that designing an optimal coordination mechanism is difficult, we concentrate on an algorithm that is able to find a (non-trivial) coordination mechanism that is not always minimal. We then discuss some subclasses of plan-coordination instances where this algorithm performs very badly, but also some class of instances where a nearly optimal coordination mechanism is returned.

U2 - 10.1007/978-3-540-88833-8_1

DO - 10.1007/978-3-540-88833-8_1

M3 - Chapter

SN - 978-3-540-88832-1

T3 - LNCS

SP - 1

EP - 21

BT - Computational Logic in Multi-Agent Systems

A2 - Sadri, F.

A2 - Satoh, K.

PB - Springer

CY - Berlin

ER -

Steenhuisen JR, Witteveen C, Zhang Y. Plan coordination mechanisms and the price of autonomy. In Sadri F, Satoh K, editors, Computational Logic in Multi-Agent Systems: 8th International Workshop, CLIMA VIII, Porto, Portugal, September 10-11, 2007. Revised Selected and Invited Papers. Berlin: Springer. 2008. p. 1-21. (LNCS). https://doi.org/10.1007/978-3-540-88833-8_1