家庭仿真求解最优路径问题算法研究

刘岩恺 薛毅 （天津师范大学计算机与信息工程学院 天津 300387）

0 引言

家庭仿真项目最早为中国科技大学为测试蓝鹰“可佳”机器人智能问题求解性能设计的一个开放性测试平台。[1]立足于服务机器人高层功能的探索，侧重对服务机器人自动规划、自然语言解析、自动判断及推理能力的认知能力考查。“可佳”机器人的框架包括4个主要部件：人机对话，语言理解，任务规划和行为规划。机器人通过人机对话获得用户的服务请求，对话语言为词汇受限的自然语言。语言理解部件将对话中有用信息进行提取、分类和转换，再传递给任务规划。任务规划根据机器人知识库，计算出完成任务的规划结果，再将其发送给行为规划部件。[2]

该仿真项目是得到最优的任务规划，本文以其实现算法为重点。比赛主要分为指令语言,自然语言两个阶段。比赛的评分公式如下：问题得分=10×完成的目标数目+5×维护的约束数目×完成的目标数目-3×行动个数-其他行动个数。[1]

1 关于最优化问题

在遵守指定约束的前提下，自动规划任务问题得分与move原子动作的发生频率相关，用尽可能少的move动作完成尽可能多的目标任务，这就是最优化问题的关键。

2 求解最优路径问题

针对上述求解最优路径问题的分析提出两种解决策略：一种是最优策略算法，在准确分析确定目标任务以及指定场景后，根据比赛的规则和实际情况对目标任务进行合并以及排序；另一种是目前比较主流而且相对比较稳定的回答集编程。

2.1 最优策略算法

2.1.1 建立世界模型 建立世界模型需要对现实场景及目标任务进行抽象，并在程序每次执行过程中通过相关函数完成对特定场景及目标任务进行描述和刻画。建立世界模型的成功与否，将直接影响到自动规划中机器人对当前场景认知的把握程度。

2.1.2 搜索优化 目标任务的初始化是建立在以搜索目标物体在世界模型中的具体信息的基础上的。下面举例分析搜索函数在程序设计中存在的难点。

①假设场景文件中有如下描述：

bottle（25）.green（25）.bottle（26）.red（26）.

任务文件中有如下要求：

puton（green bottle,worktable）.give（human,bottle）.

若搜索函数每次只顺序搜索到类型为bottle的物体即刻中止搜索，最终结果为give（human,green bottle），两个任务将都不能执行完成。此种问题解决方案为：设定目标物体标识位，凡是已定目标物体对于二次搜索为透明的。

②承接a中场景的描述假如任务文件有如下描述：

give（human,bottle）.puton（green bottle,worktable）.

结合①的解决方案，会发现此时将无法找到green bottle，因此针对①提出的解决方案，我们需要在①中完善的是：当目标物体第一次无法找到的时候，将在已确定为目标物体的集合中二次搜索，找到green bottle之后，give任务中的目标物体bottle再从未确定为目标物体的集合中搜索。

③假如场景中有如下描述：

bottle（26）.green（26）.bottle（27）.bottle（25）.red（25）.

在任务文件中有如下要求：

give（human,bottle）.puton（bottle,worktable）.puton（green,bottle,worktable）.

在此情况下，会发现在搜索过程中，没有颜色约束的物体最好搜索到最佳匹配的，即无颜色描述的物体，只有在没有找到最佳匹配物体之后，再去搜索有颜色约束的物体。

由以上3种情况分析，搜索函数优化：首先，确定为目标的物体设定标志位。其次，在顺序搜索的前提下，首次搜索必须是搜索最佳匹配目标物体。最后，只有在搜索完未被确定目标集合后，才会对已确定目标集合进行二次搜索，并再次在未确定目标集合中寻找已确定目标物体的替代物体。

2.1.3 任务动作的排序与合并 在任务目标中，假定机器人不在任务目标的位置上，那么 give（human，obj1），puton（obj1，obj2），putin（obj1，obj2）需要两次 move（A）原子动作，设定为 A类任务动作；而 putdown（obj1）|pickup（obj1）|opendoor（obj2）要一次 move（A），设定为 B类任务动作；而 goto（obj1）需要 1次move（A），设定为C类动作。在A类任务动作中，除了give（human，obj1），obj1为 big外，其他动作的 obj1均为 small。B类任务动作中，是机器人应该在完成所有任务之后保持的状态。C类任务动作很明显应该为机器人的终结动作。

当机器人在执行A类任务动作的时候，刚好有B类中obj1物体时，可以进行同源任务动作合并；当有B类中obj2时，可以进行同目标合并。同理也会有A类任务动作与A类任务动作中同源或同目标动作的合并。在理想情况下，针对每一种情况，程序中都会有相应的处理分支。但是，由于最优策略算法接近于手动实现穷举法，因此针对部分特殊情况的规划结果并不令人满意。

2.2 回答集编程

2.2.1 回答集编程介绍 在人工智能研究方面，回答集编程作为具有非单调推理能力的知识表示和推理的一般工具，在将智能符号推理形式化刻画的前提下，来实现机器人自主决策，人机交互等认知功能。下面以家庭仿真比赛项目为平台进行介绍，具体包括：使用ASP刻画设定环境的初始化情况，机器人的行动效果，初始化任务目标，将机器人中的推理任务（包括规划和诊断），转换为求解相应回答及编程程序的回答集。[3-4]

2.2.2 回答集编程求解 在自然语言比赛项目中，特定指令通过语言理解部件被转换为内部逻辑公式，此过程中需要借助常例化工具Grounder，[5]任务规划部件将这些公式作为事实直接添加到ASP程序中，形成必须满足的目标状态。回答集编程程序的求解实际上相当于通过经典规划方式，得到最优化行动序列。接下来举例说明使用回答集编程进行描述的3个基本步骤。[5]

第一步：生成所有潜在可能的解。

通过loc（X）、obj（A）和small（A）3个域谓词来推出机器人所有可能的动作，这3个域谓词的初始化是由规划的环境描述文件完成的。

第二步：用约束消除不符合的解。

任务规划程序中用not和constraints的方式来满足目标。比如说在执行自动规划过程中指定约束不能到B物体，在程序中描述如下：:-notgoal［goto（B），t］，goto（B），obj（B）.

第三步：定义在约束中出现的辅助谓词。

若任务中有要求机器人catch（A），那么我们需要做出的判断为机器人是否与其在同一处，若在，直接采用catch动作，若不在则先执行goto（X）动作，然后在再执行catch动作。要实现这些目标，使初始环境变换到目标环境需要机器人的对环境进行改变，不但需要定义机器人原子动作的执行条件，而且也需要定义执行效果，从而为机器人的下一步执行提供依据。

整个任务规划问题可以归为回答集编程程序求解问题。采用iclingo[5]求解器进行迭代求解，穷举所有的行动序列组合从而得到最优行动序列。需要注意的是穷举虽然能够得到目标结果，但是当规划任务过大时，由于规划的步数太多从而出现超时，下面是在理论基础上进行的求解效率优化方法。

第一种是从描述规划问题角度优化。

静态因果定律：动作的间接效果或一些受其他的谓词影响的谓词。

惯性定律：动作改变了其中一些谓词，但是没有被动作改变的那些谓词，其值保持不变。

第二种是从常例化过程中采用增量求解方法，可以判断当前第i步是否实现目标，若没有，则会在此基础上进行第i+1步规划。

综上所述，回答集编程具有很好的扩展性，而且在不限定时间的前提下，能够穷举得出最有行动序列，其效率仍需进一步改善。

3 总结

本文以家庭仿真比赛为背景，分别介绍了用于任务规划的最优策略算法以及回答集编程，并对当前在提高回答集编程求解效率方面的方法进行了研究。

[1]吉建民.提高ASP效率的若干途径及服务机器人上应用[D].中国科学技术大学,2010.

[2]吉建民，陈小平，姜节汇，等.一种支持个性化协调的服务机器人体系结构[J].南京大学学报：自然科学版，2010，46（2）：131-139.

[3]Gelfond,M.，Lifschitz,V.The Stable Model Semantics For Logic Programming[M].In Proceedings of the Fif th International Conference on Logic Programming（ICLP-88），1988：1070-1080.

[4]Gelfond,M.and Lifschitz,V.Classical Negation in Logic Programs and Disjunctive Databases[J].New Generation Computing，1991（9）:365-385.

[5]Martin Gebser,Roland Kaminski,Benjamin Kaufmann,etal.A User’s Guide to gringo,clasp,clingo and iclingo[Z].