Fully Observable Non-Deterministic (FOND) planning models uncertainty through actions with non-deterministic effects. Existing FOND planning algorithms are effective and employ a wide range of techniques. However, most of the existing algorithms are not robust for dealing with both non-determinism and task size. In this paper, we develop a novel iterative depth-first search algorithm that solves FOND planning tasks and produces strong cyclic policies. Our algorithm is explicitly designed for FOND planning, addressing more directly the non-deterministic aspect of FOND planning, and it also exploits the benefits of heuristic functions to make the algorithm more effective during the iterative searching process. We compare our proposed algorithm to well-known FOND planners, and show that it has robust performance over several distinct types of FOND domains considering different metrics.
翻译:完全可观察的非确定性(FOND)规划模型的不确定性,通过具有非确定性效果的行动。现有的FOND规划算法是有效的,并且采用广泛的技术。然而,大多数现有的算法对于处理非确定性和任务大小都不够健全。在本文件中,我们开发了一种新的迭代深度第一搜索算法,解决FOND规划任务并产生强有力的循环政策。我们的算法是为FOND规划设计的,更直接地处理FOND规划的非确定性方面,它还利用超常功能的好处,使该算法在迭接搜索过程中更加有效。我们把我们提议的算法与众所周知的FOND规划者进行比较,并表明它在若干不同的类型FOND领域具有强大的性能,考虑到不同的指标。