论文标题
使用树搜索和图形神经网络求解具有不确定性的分离时间网络
Solving Disjunctive Temporal Networks with Uncertainty under Restricted Time-Based Controllability using Tree Search and Graph Neural Networks
论文作者
论文摘要
在不确定性下进行计划是人工智能感兴趣的领域。我们提出了一种基于树木搜索和图形机器学习的新方法，用于调查问题，即具有不确定性的分离时间网络（DTNU）。 DTNUS的动态可控性（DC）寻求一个反应性调度策略，以满足不可控制的动作持续时间的时间约束。我们介绍了用于反应性调度的新语义：基于时间的动态可控性（TDC）和TDC，R-TDC的受限子集。我们设计了树搜索算法，以确定DTNU是否为R-TDC。此外，我们利用图形神经网络作为树木搜索指导的启发式。最后，我们对已知基准进行实验进行了实验，在该基准测试基准上，我们向R-TDC展示了在DC方面保留重要的完整性，同时更快地证明了R-TDC。这导致R-TDC中的树木搜索处理比最先进的DC求解器在DC中以相同的时间预算高出50％。我们还观察到，图形神经网络搜索指导可在更复杂的DTNU的基准上获得可观的性能增长，而解决的问题比基线树搜索要多11倍。
Planning under uncertainty is an area of interest in artificial intelligence. We present a novel approach based on tree search and graph machine learning for the scheduling problem known as Disjunctive Temporal Networks with Uncertainty (DTNU). Dynamic Controllability (DC) of DTNUs seeks a reactive scheduling strategy to satisfy temporal constraints in response to uncontrollable action durations. We introduce new semantics for reactive scheduling: Time-based Dynamic Controllability (TDC) and a restricted subset of TDC, R-TDC. We design a tree search algorithm to determine whether or not a DTNU is R-TDC. Moreover, we leverage a graph neural network as a heuristic for tree search guidance. Finally, we conduct experiments on a known benchmark on which we show R-TDC to retain significant completeness with regard to DC, while being faster to prove. This results in the tree search processing fifty percent more DTNU problems in R-TDC than the state-of-the-art DC solver does in DC with the same time budget. We also observe that graph neural network search guidance leads to substantial performance gains on benchmarks of more complex DTNUs, with up to eleven times more problems solved than the baseline tree search.
