并行概率规划综述*

自动规划是人工智能的重要分支。它针对特定领域的特定问题,生成一个由可应用动作构成的规划。经典规划中的动作效果是确定的,且在每个时间步内只能执行一个动作。但在实际问题中,动作的效果往往是不确定性的,且动作的执行具有并发性。因此,并行概率规划(Parallel and Probabilistic Planning, PPP) 被提出,并在近两次国际规划比赛中有了专门的PPP比赛。PPP的应用前景正在引起规划研究学术圈的关注。有鉴于此,本文对其进行综述。具体内容包括定义PPP领域、问题和规划解,介绍其描述语言、基准领域及规划器,并对其中两个有代表性的规划器进行实际测试。实验表明在求解效率方面测试结果与比赛结果基本一致,但部分规划器的求解规模与竞赛不完全一致。这可能是比赛中的某些未开源代码或手工干预得到的。

Survey on the Parallel and Probabilistic Planning

Automated planning is an important branch in the Artificial Intelligence field. Given a specific domain and problem, it will generate plan solutions composed of applicable actions. In classic planning, actions have deterministic effects and are carried out sequentially. However, in real-world problems, the effects of an action might be non-deterministic and there might be concurrent actions. Therefore, researchers proposed the Parallel and Probabilistic Planning (PPP). Further, the planning community proposed a special track for PPP in the newest two International Planning Competitions (IPCs). The PPP has a strong application perspective and is drawing a great deal of attention in the planning community. Therefore, this paper presented a survey on the PPP. It first gave formal definitions of domains, problems and plan solutions of the PPP. It then introduced competition languages, benchmark domains and competitive planners in the PPP. Finally, it tested two representative planners. Experiment results showed that, for the efficiency, the results were similar to those in the competitions. However, the scalability was different. It might be caused by some unpublished source codes or some manual intervention.