首页    期刊浏览 2024年11月08日 星期五
登录注册

文章基本信息

  • 标题:A Game-Theoretic Approach to Timeline-Based Planning with Uncertainty
  • 本地全文:下载
  • 作者:Nicola Gigante ; Angelo Montanari ; Marta Cialdea Mayer
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2018
  • 卷号:120
  • 页码:1-17
  • DOI:10.4230/LIPIcs.TIME.2018.13
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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.
  • 关键词:Timeline-based planning with uncertainty; strategic games; decidability
国家哲学社会科学文献中心版权所有