并行概率规划综述

Survey on parallel and probabilistic planning

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

Given a specific domain and problem,automated planning 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,the parallel and probabilistic planning（ PPP） was proposed. 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. Then it introduced competition languages,benchmark domains and competitive planners in the PPP. Finally,it tested two representative planners. Experiment results show 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.