Incorporating Decision Nodes into Conditional Simple Temporal Networks
Incorporating Decision Nodes into Conditional Simple Temporal Networks
复制标题
将决策节点合并到条件简单时态网络中
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Matteo Zavatteri
中科院分区：
文献类型：
--
作者：
Massimo Cairo;Combi Carlo;Carlo Comin;Luke Hunsberger;Roberto Posenato;Romeo Rizzi;Matteo Zavatteri
条件简单时态网络（Conditional Simple Temporal Network，CSTN）是对简单时态网络（Simple Temporal Network，CSTN）的扩充，包含了特殊的时间点，称为观测时间点。在一个时间节点中，执行网络的代理控制每个时间点的执行。然而，每个观察时间点都有一个与之相关联的唯一命题字母，当代理执行该时间点时，环境会为相应的字母分配一个真值。因此，代理观察，但不控制真值的分配。如果存在一个执行其时间点的策略，使得无论环境将哪个真值分配给命题字母，所有相关约束都将得到满足，则Cynchronous是动态一致的（DC）。
或者，在标记简单时间网络（Labeled Simple Temporal Network，也称为选择时间计划）中，执行网络的智能体控制对所谓的选择变量的赋值。此外，代理可以随时进行这些分配。基于这个原因，一个标记的时间网络等价于一个析取的时间网络。
本文结合了上述两个扩展，增加了CCENTRAL，不仅包括观察时间点，但也决策时间点。决策时间点就像观察时间点，因为它有一个相关的命题字母，其值在执行决策时间点时确定。它的不同之处在于代理-而不是环境-选择该值。由此产生的网络被称为具有决策的CSTND（CSTND）。本文证明了CSTND是CSTNs和Labeled STNs的推广，并证明了确定任何给定的CSTND是否动态一致的问题是PSPACE完全的。它还提出了解决CSTND的两个子类的算法：
(1)那些只包含决策时间点;（2）那些在执行开始之前做出所有决策的时间点。
A Conditional Simple Temporal Network (CSTN) augments a Simple Temporal Network (STN) to include special time-points, called observation time-points. In a CSTN, the agent executing the network controls the execution of every time-point. However, each observation time-point has a unique propositional letter associated with it and, when the agent executes that time-point, the environment assigns a truth value to the corresponding letter. Thus, the agent observes but, does not control the assignment of truth values. A CSTN is dynamically consistent (DC) if there exists a strategy for executing its time-points such that all relevant constraints will be satisfied no matter which truth values the environment assigns to the propositional letters.
Alternatively, in a Labeled Simple Temporal Network (Labeled STN) - also called a Temporal Plan with Choice - the agent executing the network controls the assignment of values to the so-called choice variables. Furthermore, the agent can make those assignments at any time. For this reason, a Labeled STN is equivalent to a Disjunctive Temporal Network.
This paper incorporates both of the above extensions by augmenting a CSTN to include not only observation time-points but also decision time-points. A decision time-point is like an observation time-point in that it has an associated propositional letter whose value is determined when the decision time-point is executed. It differs in that the agent - not the environment - selects that value. The resulting network is called a CSTN with Decisions (CSTND). This paper shows that a CSTND generalizes both CSTNs and Labeled STNs, and proves that the problem of determining whether any given CSTND is dynamically consistent is PSPACE-complete. It also presents algorithms that address two sub-classes of CSTNDs:
(1) those that contain only decision time-points; and (2) those in which all decisions are made before execution begins.