摘要

本文由Sabah Binte Noor和Fazlul Hasan Siddiqui共同撰写，主要探讨了在部分顺序计划（Partial-Order Plan, POP）中通过块替换（Block Substitution）提高执行并发性的方法。文章首先定义了在POP中实现动作并行执行的必要和充分条件，然后提出了一种算法，通过优化资源利用率来增强计划的并发性。该算法通过消除计划中的动作顺序限制，并将子计划替换为计划外动作，从而提高计划的灵活性。实验结果显示，该方法在25%的计划中显著提高了并发性，总体并发性提高了2.1%。

原理

文章提出的方法通过以下几个关键步骤提高计划的并发性：

1. 定义非并发约束条件：文章首先定义了在POP中实现动作并行执行的必要和充分条件，即动作间的非并发约束条件，这些条件指定了哪些动作不能并行执行。
2. 块去顺序化（Block Deordering）：通过将连贯的动作集封装成块（Block），消除计划中的顺序约束，从而允许动作在不同的序列中执行。
3. 块替换（Block Substitution）：引入了一种算法，通过优化资源利用率，将计划中的子计划替换为计划外的动作，进一步提高计划的并发性。
4. 实验验证：通过在基准问题上的实验，验证了该方法在提高计划并发性方面的有效性。

流程

1. 初始化：从部分顺序计划（POP）开始，该计划允许动作在不同的序列中执行。
2. 块去顺序化：将连贯的动作集封装成块，消除计划中的顺序约束。
3. 块替换：通过替换计划中的子计划，引入计划外的动作，优化资源利用率，提高计划的并发性。
4. 验证与优化：通过实验验证替换后的计划并发性是否提高，并根据结果进一步优化算法。

例如，在电梯领域的一个计划中，通过块去顺序化和块替换，成功地将原本不能并行执行的动作转换为可以并行执行的动作，从而提高了计划的并发性。

应用

该方法在人工智能规划领域具有广泛的应用前景，特别是在需要高度并发执行的场景中，如多机器人协作、复杂系统管理等。通过提高计划的并发性，可以显著减少计划的总体执行时间，提高系统的效率和响应速度。此外，该方法还可以应用于计划的重用、修改和分解，进一步扩展其应用范围。