DROPS

Document

DOI: 10.4230/LIPIcs.TIME.2018.13

A Game-Theoretic Approach to Timeline-Based Planning with Uncertainty

Authors: Nicola Gigante, Angelo Montanari, Marta Cialdea Mayer, Andrea Orlandini, and Mark Reynolds

Published in: LIPIcs, Volume 120, 25th International Symposium on Temporal Representation and Reasoning (TIME 2018)

Abstract

In timeline-based planning, domains are described as sets of independent, but interacting, components, whose behaviour over time (the set of timelines) is governed by a set of temporal constraints. A distinguishing feature of timeline-based planning systems is the ability to integrate planning with execution by synthesising control strategies for flexible plans. However, flexible plans can only represent temporal uncertainty, while more complex forms of nondeterminism are needed to deal with a wider range of realistic problems. In this paper, we propose a novel game-theoretic approach to timeline-based planning problems, generalising the state of the art while uniformly handling temporal uncertainty and nondeterminism. We define a general concept of timeline-based game and we show that the notion of winning strategy for these games is strictly more general than that of control strategy for dynamically controllable flexible plans. Moreover, we show that the problem of establishing the existence of such winning strategies is decidable using a doubly exponential amount of space.

Cite as

Nicola Gigante, Angelo Montanari, Marta Cialdea Mayer, Andrea Orlandini, and Mark Reynolds. A Game-Theoretic Approach to Timeline-Based Planning with Uncertainty. In 25th International Symposium on Temporal Representation and Reasoning (TIME 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 120, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gigante_et_al:LIPIcs.TIME.2018.13,
  author =	{Gigante, Nicola and Montanari, Angelo and Cialdea Mayer, Marta and Orlandini, Andrea and Reynolds, Mark},
  title =	{{A Game-Theoretic Approach to Timeline-Based Planning with Uncertainty}},
  booktitle =	{25th International Symposium on Temporal Representation and Reasoning (TIME 2018)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-089-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{120},
  editor =	{Alechina, Natasha and N{\o}rv\r{a}g, Kjetil and Penczek, Wojciech},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2018.13},
  URN =		{urn:nbn:de:0030-drops-97786},
  doi =		{10.4230/LIPIcs.TIME.2018.13},
  annote =	{Keywords: Timeline-based planning with uncertainty, strategic games, decidability}
}

Document

DOI: 10.4230/DagRep.7.1.32

Planning and Robotics (Dagstuhl Seminar 17031)

Authors: Malik Ghallab, Nick Hawes, Daniele Magazzeni, Brian C. Williams, and Andrea Orlandini

Published in: Dagstuhl Reports, Volume 7, Issue 1 (2017)

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 17031 on "Planning and Robotics". The seminar was concerned with the synergy between the research areas of Automated Planning & Scheduling and Robotics. The motivation for this seminar was to bring together researchers from the two communities and people from the Industry in order to foster a broader interest in the integration of planning and deliberation approaches to sensory-motor functions in robotics. The first part of the seminar was dedicated to eight sessions composed on several topics in which attendees had the opportunity to present position statements. Then, the second part was composed by six panel sessions where attendees had the opportunity to further discuss the position statements and issues raised in previous sessions. The main outcomes were a greater common understanding of planning and robotics issues and challenges, and a greater appreciation of crossover between different perspectives, i.e., spanning from low level control to high-level cognitive approaches for autonomous robots. Different application domains were also discussed in which the deployment of planning and robotics methodologies and technologies constitute an added value.

Cite as

Malik Ghallab, Nick Hawes, Daniele Magazzeni, Brian C. Williams, and Andrea Orlandini. Planning and Robotics (Dagstuhl Seminar 17031). In Dagstuhl Reports, Volume 7, Issue 1, pp. 32-73, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{ghallab_et_al:DagRep.7.1.32,
  author =	{Ghallab, Malik and Hawes, Nick and Magazzeni, Daniele and Williams, Brian C. and Orlandini, Andrea},
  title =	{{Planning and Robotics (Dagstuhl Seminar 17031)}},
  pages =	{32--73},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{1},
  editor =	{Ghallab, Malik and Hawes, Nick and Magazzeni, Daniele and Williams, Brian C. and Orlandini, Andrea},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.1.32},
  URN =		{urn:nbn:de:0030-drops-72451},
  doi =		{10.4230/DagRep.7.1.32},
  annote =	{Keywords: adjustable autonomy, artificial intelligence, automated planning and scheduling, goal reasoning, human-robot interaction, plan execution, robotics}
}

Search Results

Documents authored by Orlandini, Andrea

A Game-Theoretic Approach to Timeline-Based Planning with Uncertainty

Abstract

Cite as

Planning and Robotics (Dagstuhl Seminar 17031)

Abstract

Cite as

Thanks for your feedback!

Could not send message