第15章_主体计算创新.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 史忠植 高级人工智能 * 因果链 因果链描述一个动作为另一个动作建立一个前提条件。 一个规划中，动作 E 和动作 U 之间存在因果链，当且仅当 1、 ，即 E 和 U 之间有顺序约束； 2、 使得 ，其中 ，即E的一个效果为U的一个前提； 3、 ，如果 ， 并且 ，那么 并且 ，即发生在E和U之间的所有动作都不影响 。 * 史忠植 高级人工智能 * 冲突 冲突描述的是一个因果链被其它规划中的某些动作破坏。 设存在因果链 和另一个动作C，如果 1、 并且 ，即C可能在E和U之间执行； 2、 使得 ，即C的效果之一 可能破坏 那么称C为的 一个威胁。当C在E和U之间被执行时，就发生冲突。 * 史忠植 高级人工智能 * 冲突举例 A B B 初始状态 目标状态 C A C A C 冲突状态 B * 史忠植 高级人工智能 * 冲突描述 规划： Step1=Move(?obj,?dest), Step1.obj=C, Step1.dest≠B; Step2=Move(?obj,?dest), Step2.obj=B, Step2.dest=Table; Step3=Move(?obj,?dest), Step3.obj=A, Step3.dest=B; Step4=Move(?obj,?dest), Step4.obj=C, Step4.dest=A; Step1Step2, Step2Step3, Step3Step4 当按照下面的约束执行时，发生冲突： Step1.dest=A Step3无法执行。 * 史忠植 高级人工智能 * 冲突消解方法 冲突威胁到规划的正确性，消解冲突的方法就是在规划之间添加新的约束，破坏冲突产生的条件。Chapman阐明了一个充分必要的冲突消解集合，其中包括“升级”、“降级”、“分离”和“引入修复”四种约束。 设动作的C一个效果 威胁因果链 ，那么下列任何一个约束对于消解它都是充分的： （1）升级：加入顺序约束 ， （2）降级：加入顺序约束 , （3）分离：加入新的变量约束使得 ， （4）引入修复：选择某个规划中已有动作或者新动作W，使得 ， 而且 或者 * 史忠植 高级人工智能 * 冲突消解方法举例 规划： Step1=Move(?obj,?dest), Step1.obj=C, Step1.dest≠B; Step2=Move(?obj,?dest), Step2.obj=B, Step2.dest=Table; Step3=Move(?obj,?dest), Step3.obj=A, Step3.dest=B; Step4=Move(?obj,?dest), Step4.obj=C, Step4.dest=A; Step1Step2, Step2Step3, Step3Step4 当按照下面的约束执行时，发生冲突： Step1.dest=A Step3无法执行。 消解方法： 添加约束Step1.dest≠A * 史忠植 高级人工智能 * UCPOP算法 UCPOP是一个用Common Lisp写的偏序规划器。 UCPOP算法不断修改未完成的规划直到所有目标和后续子目标都被满足。修改包括向其中加入新动作步骤，向其中加入等价或不等价绑定来约束自由变量，向中加入顺序约束来安排动作步骤的先后顺序。 * 史忠植 高级人工智能 * UCPOP算法主要步骤 UCPOP算法的主要步骤： 1．终止条件 2．选择子目标 3．选择动作 4．子目标生成 5．因果链保护 6．递归 * 史忠植 高级人工智能 * GraphPlan图规划算法 图规划算法包括两个交替进行的过程：图扩充和方案有哪些信誉好的足球投注网站。图扩充过程对规划图按时间顺序向前扩充，直到满足规划存在的必要条件（不是充分条件）。然后方案有哪些信誉好的足球投注网站过程在图中