2009-8-20 史忠植 高级人工智能 1
第十章 分布式人工智能史忠植中国科学院计算技术所
2009-8-20 史忠植 高级人工智能 2
规划规划是主体对动作进行推理的一种主要形式，它很大程度上体现了主体的智能性。同时，规划也是描述主体行为的主要方式。
规划是为了建立一个控制算法，使智能主体能够为实现目标，对动作过程进行综合。
2009-8-20 史忠植 高级人工智能 3
经典规划问题
经典的规划理论认为规划要解决的问题
（即规划的输入）是：
用某种形式语言描述的初始世界状态
用某种形式语言描述的主体目标
用某种形式语言描述的主体可能采用的动作，通常也叫做领域知识
输出是：
可以在某个满足初始状态描述的世界中执行并达到主体目标的一个动作序列
2009-8-20 史忠植 高级人工智能 4
经典规划的假设
原子执行时间
确定性结果
主体全知
主体唯一能动性
2009-8-20 史忠植 高级人工智能 5
经典规划系统
人们对经典规划算法进行了大量的研究，提出了许多有效的算法，如
STRIPS,TWEAK,UCPOP和 SNLP等。
最近，其它领域中的一些有效算法被引入到规划中来。新的进展主要在
GraphPlan和 SATPLAN方面。
2009-8-20 史忠植 高级人工智能 6
STRIPS表示法
世界状态,一个世界状态（或简称为状态）是一组谓词的集合。
目标：表示世界状态的谓词的合取。
动作：动作用前提条件和动作效果来表示。
前提条件：动作执行前必须满足的状态。
动作效果：动作执行后可以保证为真的状态。
2009-8-20 史忠植 高级人工智能 7
STRIPS表示法 -规划
动作模板：表示一组可能的动作，即包含自由变量的动作。
动作步骤：表示一个具体的动作，由动作模板中的变量添加约束得到。
规划：规划用动作步骤和动作步骤上的约束来表示。约束包括：
动作步骤间的顺序约束，根据顺序约束可以分为全序规划和偏序规划。
动作步骤中变量或常量之间的等价、
不等价、大于、小于等约束。
2009-8-20 史忠植 高级人工智能 8
经典规划举例
A
B
B
A
初始状态 目标状态
2009-8-20 史忠植 高级人工智能 9
规划表示初始状态：
On(table,A),On(A,B)
目标状态：
On(B,A),On(table,B)
基本知识：
动作模板：
Move(?Obj,?dest)
precondition,Clear(?Obj)
effect,delete,On(?Obj,?src)
add,On(?Obj,?dest)
2009-8-20 史忠植 高级人工智能 10
希望得到的规划结果希望得到的结果：
第一步,Move(B,table)
第二步,Move(A,B)
实际的表示为：
Step1.Action=Move,Step1.Obj=B,Step1.dest=table,
Step2.Action=Move,Step2.Obj=A,Step2.dest=B,
Step1 < Step2
2009-8-20 史忠植 高级人工智能 11
规划算法规划算法实质上是一种搜索算法。搜索一个动作步骤序列，使得经过这个动作步骤的作用后，世界状态由初始状态变化为目标状态。算法应包含以下功能：
选择动作：选择当前状态下能够执行的动作。
变量绑定（匹配）：根据当前状态，对动作中的变量进行约束。
回溯：发现死锁状态后，可以回退到以前的某个状态。
2009-8-20 史忠植 高级人工智能 12
规划搜索初始状态状态 1-1 状态 1-n
状态 m-k
目标状态动作 1-1 动作 1-n
动作 m-k
…… ……
……
2009-8-20 史忠植 高级人工智能 13
规划结果初始状态,On(table,A),On(A,B)
On(table,A),On(table,B)
目标状态,On(B,A),On(table,B)
Move(B,table)
Move(A,B)
2009-8-20 史忠植 高级人工智能 14
冲突一个规划正确的必要条件是，在规划的每个实现中，每个动作的每个前提条件在动作执行之前都满足。造成规划不正确的原因是一个动作会破坏其他动作间的因果链，即冲突。
2009-8-20 史忠植 高级人工智能 15
因果链因果链描述一个动作为另一个动作建立一个前提条件 。
一个规划中,动作 E 和动作 U 之间存在因果链,当且仅当
1、,即 E 和 U 之间有顺序约束；
2,使得,其中,即 E的一个效果为 U
的一个前提；
3、,如果,并且,那么并且,即发生在 E和 U之间的所有动作都不影响 。
OOUE?)(?
EE Ee )( UE pe? UU Pp?
T? )( TE? )( UT? TT Ee )( UT pe
)( UT pe Up
2009-8-20 史忠植 高级人工智能 16
冲突冲突描述的是一个因果链被其它规划中的某些动作破坏 。
设存在因果链 和另一个动作 C,如果
1,并且,即 C可能在 E和 U之间执行；
2,使得,即 C的效果之一 可能破坏那么称 C为的 一个威胁 。 当 C在 E和 U之间被执行时,
就发生冲突 。
UpE U,,
)( EC )( CU
CC Ee )( UC pe Ce Up
UpE U,,
2009-8-20 史忠植 高级人工智能 17
冲突举例
A
B
B
初始状态 目标状态
C
A
C
A
C
冲突状态
B
2009-8-20 史忠植 高级人工智能 18
冲突描述规划：
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;
Step1<Step2,Step2<Step3,Step3<Step4
当按照下面的约束执行时,发生冲突：
Step1.dest=A
Step3无法执行 。
2009-8-20 史忠植 高级人工智能 19
冲突消解方法冲突威胁到规划的正确性,消解冲突的方法就是在规划之间添加新的约束,破坏冲突产生的条件 。 Chapman阐明了一个充分必要的冲突消解集合,其中包括,升级,,
,降级,,,分离,和,引入修复,四种约束 。
设动作的 C一个效果 威胁因果链,那么下列任何一个约束对于消解它都是充分的：
（ 1） 升级：加入顺序约束,
（ 2） 降级：加入顺序约束,
（ 3） 分离：加入新的变量约束使得,
（ 4） 引入修复：选择某个规划中已有动作或者新动作 W，
使得,而且 或者
Ce UpE U,,
CU?
EC?
CU ep?
WW Ee UWC )( UW pe? )( CW ee
2009-8-20 史忠植 高级人工智能 20
冲突消解方法举例规划：
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;
Step1<Step2,Step2<Step3,Step3<Step4
当按照下面的约束执行时,发生冲突：
Step1.dest=A
Step3无法执行 。
消解方法：
添加约束 Step1.dest≠A
2009-8-20 史忠植 高级人工智能 21
UCPOP算法
UCPOP是一个用 Common Lisp写的偏序规划器。
UCPOP算法不断修改未完成的规划直到所有目标和后续子目标都被满足。修改包括向其中加入新动作步骤，向其中加入等价或不等价绑定来约束自由变量，向中加入顺序约束来安排动作步骤的先后顺序。
2009-8-20 史忠植 高级人工智能 22
UCPOP算法主要步骤
UCPOP算法的主要步骤：
1．终止条件
2．选择子目标
3．选择动作
4．子目标生成
5．因果链保护
6．递归
2009-8-20 史忠植 高级人工智能 23
GraphPlan图规划算法图规划算法包括两个交替进行的过程：图扩充和方案搜索。图扩充过程对规划图按时间顺序向前扩充，直到满足规划存在的必要条件（不是充分条件）。然后方案搜索过程在图中进行反向链搜索，
寻找解决问题的方案。如果没有找到解决方案，则进一步扩充规划图，重复上述循环。
2009-8-20 史忠植 高级人工智能 24
规划图中的节点
2009-8-20 史忠植 高级人工智能 25
规划图中动作间的互斥关系第 i层的两个动作实例是互斥的，如果下列条件中至少有一条成立：
不一致效果：一个动作的效果是另一个动作效果的否定；
干涉：一个动作删除了另一个动作的前提；
竞争的需求：两个动作在 i-1层中具有互斥的前提。
第 i层的两个状态是互斥的，如果
一个状态是另一个状态的否定，或者
获得两个状态的方法（ i-1层中的动作）是两两互斥的（不一致支持）。
2009-8-20 史忠植 高级人工智能 26
互斥关系的图形表示
2009-8-20 史忠植 高级人工智能 27
多主体环境下的规划问题多主体系统规划的特殊之处在于：
主体可以请求其它主体协作执行一个联合动作来实现自己的目标。
主体之间的动作冲突必须通过主体之间的协商来避免。
2009-8-20 史忠植 高级人工智能 28
协作动作举例
A
B
B
A
初始状态 目标状态
agent1 agent2
2009-8-20 史忠植 高级人工智能 29
协作动作的表示动作模板：
Move(?Obj,?dest)
actor,actor1
precondition,Clear(?Obj) and (Weight(?Obj,?x) and?x<=3)
delete,On(?Obj,?src)
add,On(?Obj,?dest)
Joint-Move(?Obj,?dest)
actor,actor1,actor2
precondition,Clear(?Obj) and (Weight(?Obj,?x) and 3<?x<=6)
delete,On(?Obj,?src)
add,On(?Obj,?dest)
物体,Weight(A,4),Weight(B,1)
初始状态：
On(table,A),On(A,B)
目标状态：
On(B,A),On(table,B)
2009-8-20 史忠植 高级人工智能 30
任务分配规划结果如下：
Step1.Action=Move,Step1.Obj=B,Step1.dest=table,
Step2.Action=Joint-Move,Step2.Obj=A,Step2.dest=B,
Step1 < Step2
然后根据主体能力库，对动作步骤中的角色进行任务分配。
主体能力库如下：
agent1,CanDo Move as actor1
CanDo Joint-Move as actor1,actor2
agent2,CanDo Joint-Move as actor1,actor2
需要分配的角色：
Step1(Move).actor1,可选主体 {agent1}
Step2(Joint-Move).actor1,可选主体 {agent1,agent2}
Step2(Joint-Move).actor2,可选主体 {agent1,agent2}
2009-8-20 史忠植 高级人工智能 31
规划间的冲突规划间冲突分两种：
目标冲突：两个规划的目标冲突。
动作冲突：一个规划中的一个动作会破坏另一个规划中的一个动作的前提。
解决方法：
目标冲突：放弃一个不太重要的目标。
动作冲突：在动作之间添加时序约束。
2009-8-20 史忠植 高级人工智能 32
规划间冲突举例
A
B
B
初始状态 agent1目标状态
agent1 agent2 Agent３
C
A
C
A
C
agent3目标状态
2009-8-20 史忠植 高级人工智能 33
规划间冲突举例
agent1的目标,On(B,Table),On(A,B),On(C,A)
规划,Move(B,Table),Move(A,B),Move(C,A)
agent2的目标,On(C,A)
规划,Move(B,Table),Move(C,A)
当按照下面的顺序执行时,发生冲突：
Agent1,Move(B,Table)
Agent2,Move(C,A)
Agent1,Move(A,B)无法执行
2009-8-20 史忠植 高级人工智能 34
规划间冲突消解方法规划间冲突的消解方法也是添加约束,包括顺序约束和变量绑定约束,不过这些约束是在规划之间的约束 。
规划间的约束要靠多个主体的协调来实现 。
顺序约束：动作执行过程中添加同步动作
WaitFor和 Inform。
变量绑定约束：主体之间通信传递变量约束的更新 。
2009-8-20 史忠植 高级人工智能 35
冲突消解方法举例
agent1的规划：
Move(B,Table),Move(A,B),Move(C,A)
agent2的规划：
Move(B,Table),Move(C,A)
当按照下面的顺序执行时,发生冲突：
Agent1,Move(B,Table)
Agent2,Move(C,A)
Agent1,Move(A,B)无法执行消解方法：
升级：添加顺序约束 agent1.Move(A,B)<agent2.Move(C,A)
2009-8-20 史忠植 高级人工智能 36
约束一致性通过添加新约束的方法可以消解冲突，但是新约束可能会与原有的约束发生矛盾。
矛盾分为两种：
顺序约束不一致
变量绑定约束不一致
2009-8-20 史忠植 高级人工智能 37
顺序约束不一致顺序约束不一致 。 令 和 为两个顺序约束的集合,
与 在多个主体的规划中矛盾,当且仅当使得：
并且 。
例如,agent1.step1<agent2.step1
agent2.step1<agent1.step2
agent1.step2<agent1.step1
1R 2R
1R 2R SO,
)()( 1 OORTR )()( 2 OORTR
2009-8-20 史忠植 高级人工智能 38
变量绑定约束不一致令 和 为两个等价和不等价约束的集合 。 令 为
R中所有等价约束,为 R中所有不等价约束 。
与 在多个主体的规划中矛盾,当且仅当存在变量 x和 y
使得：
而且
。
例如,agent1.step1.dest=agent2.step1.obj
agent1.step1.dest=A
agent2.step1.obj=B
1R 2R )(RCo
)(RNonco
1R 2R
))()(()( 21 CoRCoRCoERyx
))()(()( 21 N o n coRN o n coRN o n coyx
2009-8-20 史忠植 高级人工智能 39
多主体规划的过程
1) 规划生成动作步骤
2) 检测规划间的冲突
3) 如果检测到冲突，则消解冲突
4) 添加约束消解冲突时，要进行约束一致性判断
5) 任务分配
2009-8-20 史忠植 高级人工智能 40
多主体规划的两种基本方式
集中式规划：由中央协调主体来进行规划，
然后将规划结果分配给各主体执行。缺点是当任务很多，或者很复杂时，中央协调主体的负担很重，成为系统的瓶颈。
分布式规划：每个主体自行进行规划，冲突的检测和消解通过主体间的协商解决。
缺点是冲突的检测和消解比较困难。
2009-8-20 史忠植 高级人工智能 41
新的研究方向
动态规划
条件规划
概率规划
不完备信息规划
第十章 分布式人工智能史忠植中国科学院计算技术所
2009-8-20 史忠植 高级人工智能 2
规划规划是主体对动作进行推理的一种主要形式，它很大程度上体现了主体的智能性。同时，规划也是描述主体行为的主要方式。
规划是为了建立一个控制算法，使智能主体能够为实现目标，对动作过程进行综合。
2009-8-20 史忠植 高级人工智能 3
经典规划问题
经典的规划理论认为规划要解决的问题
（即规划的输入）是：
用某种形式语言描述的初始世界状态
用某种形式语言描述的主体目标
用某种形式语言描述的主体可能采用的动作，通常也叫做领域知识
输出是：
可以在某个满足初始状态描述的世界中执行并达到主体目标的一个动作序列
2009-8-20 史忠植 高级人工智能 4
经典规划的假设
原子执行时间
确定性结果
主体全知
主体唯一能动性
2009-8-20 史忠植 高级人工智能 5
经典规划系统
人们对经典规划算法进行了大量的研究，提出了许多有效的算法，如
STRIPS,TWEAK,UCPOP和 SNLP等。
最近，其它领域中的一些有效算法被引入到规划中来。新的进展主要在
GraphPlan和 SATPLAN方面。
2009-8-20 史忠植 高级人工智能 6
STRIPS表示法
世界状态,一个世界状态（或简称为状态）是一组谓词的集合。
目标：表示世界状态的谓词的合取。
动作：动作用前提条件和动作效果来表示。
前提条件：动作执行前必须满足的状态。
动作效果：动作执行后可以保证为真的状态。
2009-8-20 史忠植 高级人工智能 7
STRIPS表示法 -规划
动作模板：表示一组可能的动作，即包含自由变量的动作。
动作步骤：表示一个具体的动作，由动作模板中的变量添加约束得到。
规划：规划用动作步骤和动作步骤上的约束来表示。约束包括：
动作步骤间的顺序约束，根据顺序约束可以分为全序规划和偏序规划。
动作步骤中变量或常量之间的等价、
不等价、大于、小于等约束。
2009-8-20 史忠植 高级人工智能 8
经典规划举例
A
B
B
A
初始状态 目标状态
2009-8-20 史忠植 高级人工智能 9
规划表示初始状态：
On(table,A),On(A,B)
目标状态：
On(B,A),On(table,B)
基本知识：
动作模板：
Move(?Obj,?dest)
precondition,Clear(?Obj)
effect,delete,On(?Obj,?src)
add,On(?Obj,?dest)
2009-8-20 史忠植 高级人工智能 10
希望得到的规划结果希望得到的结果：
第一步,Move(B,table)
第二步,Move(A,B)
实际的表示为：
Step1.Action=Move,Step1.Obj=B,Step1.dest=table,
Step2.Action=Move,Step2.Obj=A,Step2.dest=B,
Step1 < Step2
2009-8-20 史忠植 高级人工智能 11
规划算法规划算法实质上是一种搜索算法。搜索一个动作步骤序列，使得经过这个动作步骤的作用后，世界状态由初始状态变化为目标状态。算法应包含以下功能：
选择动作：选择当前状态下能够执行的动作。
变量绑定（匹配）：根据当前状态，对动作中的变量进行约束。
回溯：发现死锁状态后，可以回退到以前的某个状态。
2009-8-20 史忠植 高级人工智能 12
规划搜索初始状态状态 1-1 状态 1-n
状态 m-k
目标状态动作 1-1 动作 1-n
动作 m-k
…… ……
……
2009-8-20 史忠植 高级人工智能 13
规划结果初始状态,On(table,A),On(A,B)
On(table,A),On(table,B)
目标状态,On(B,A),On(table,B)
Move(B,table)
Move(A,B)
2009-8-20 史忠植 高级人工智能 14
冲突一个规划正确的必要条件是，在规划的每个实现中，每个动作的每个前提条件在动作执行之前都满足。造成规划不正确的原因是一个动作会破坏其他动作间的因果链，即冲突。
2009-8-20 史忠植 高级人工智能 15
因果链因果链描述一个动作为另一个动作建立一个前提条件 。
一个规划中,动作 E 和动作 U 之间存在因果链,当且仅当
1、,即 E 和 U 之间有顺序约束；
2,使得,其中,即 E的一个效果为 U
的一个前提；
3、,如果,并且,那么并且,即发生在 E和 U之间的所有动作都不影响 。
OOUE?)(?
EE Ee )( UE pe? UU Pp?
T? )( TE? )( UT? TT Ee )( UT pe
)( UT pe Up
2009-8-20 史忠植 高级人工智能 16
冲突冲突描述的是一个因果链被其它规划中的某些动作破坏 。
设存在因果链 和另一个动作 C,如果
1,并且,即 C可能在 E和 U之间执行；
2,使得,即 C的效果之一 可能破坏那么称 C为的 一个威胁 。 当 C在 E和 U之间被执行时,
就发生冲突 。
UpE U,,
)( EC )( CU
CC Ee )( UC pe Ce Up
UpE U,,
2009-8-20 史忠植 高级人工智能 17
冲突举例
A
B
B
初始状态 目标状态
C
A
C
A
C
冲突状态
B
2009-8-20 史忠植 高级人工智能 18
冲突描述规划：
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;
Step1<Step2,Step2<Step3,Step3<Step4
当按照下面的约束执行时,发生冲突：
Step1.dest=A
Step3无法执行 。
2009-8-20 史忠植 高级人工智能 19
冲突消解方法冲突威胁到规划的正确性,消解冲突的方法就是在规划之间添加新的约束,破坏冲突产生的条件 。 Chapman阐明了一个充分必要的冲突消解集合,其中包括,升级,,
,降级,,,分离,和,引入修复,四种约束 。
设动作的 C一个效果 威胁因果链,那么下列任何一个约束对于消解它都是充分的：
（ 1） 升级：加入顺序约束,
（ 2） 降级：加入顺序约束,
（ 3） 分离：加入新的变量约束使得,
（ 4） 引入修复：选择某个规划中已有动作或者新动作 W，
使得,而且 或者
Ce UpE U,,
CU?
EC?
CU ep?
WW Ee UWC )( UW pe? )( CW ee
2009-8-20 史忠植 高级人工智能 20
冲突消解方法举例规划：
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;
Step1<Step2,Step2<Step3,Step3<Step4
当按照下面的约束执行时,发生冲突：
Step1.dest=A
Step3无法执行 。
消解方法：
添加约束 Step1.dest≠A
2009-8-20 史忠植 高级人工智能 21
UCPOP算法
UCPOP是一个用 Common Lisp写的偏序规划器。
UCPOP算法不断修改未完成的规划直到所有目标和后续子目标都被满足。修改包括向其中加入新动作步骤，向其中加入等价或不等价绑定来约束自由变量，向中加入顺序约束来安排动作步骤的先后顺序。
2009-8-20 史忠植 高级人工智能 22
UCPOP算法主要步骤
UCPOP算法的主要步骤：
1．终止条件
2．选择子目标
3．选择动作
4．子目标生成
5．因果链保护
6．递归
2009-8-20 史忠植 高级人工智能 23
GraphPlan图规划算法图规划算法包括两个交替进行的过程：图扩充和方案搜索。图扩充过程对规划图按时间顺序向前扩充，直到满足规划存在的必要条件（不是充分条件）。然后方案搜索过程在图中进行反向链搜索，
寻找解决问题的方案。如果没有找到解决方案，则进一步扩充规划图，重复上述循环。
2009-8-20 史忠植 高级人工智能 24
规划图中的节点
2009-8-20 史忠植 高级人工智能 25
规划图中动作间的互斥关系第 i层的两个动作实例是互斥的，如果下列条件中至少有一条成立：
不一致效果：一个动作的效果是另一个动作效果的否定；
干涉：一个动作删除了另一个动作的前提；
竞争的需求：两个动作在 i-1层中具有互斥的前提。
第 i层的两个状态是互斥的，如果
一个状态是另一个状态的否定，或者
获得两个状态的方法（ i-1层中的动作）是两两互斥的（不一致支持）。
2009-8-20 史忠植 高级人工智能 26
互斥关系的图形表示
2009-8-20 史忠植 高级人工智能 27
多主体环境下的规划问题多主体系统规划的特殊之处在于：
主体可以请求其它主体协作执行一个联合动作来实现自己的目标。
主体之间的动作冲突必须通过主体之间的协商来避免。
2009-8-20 史忠植 高级人工智能 28
协作动作举例
A
B
B
A
初始状态 目标状态
agent1 agent2
2009-8-20 史忠植 高级人工智能 29
协作动作的表示动作模板：
Move(?Obj,?dest)
actor,actor1
precondition,Clear(?Obj) and (Weight(?Obj,?x) and?x<=3)
delete,On(?Obj,?src)
add,On(?Obj,?dest)
Joint-Move(?Obj,?dest)
actor,actor1,actor2
precondition,Clear(?Obj) and (Weight(?Obj,?x) and 3<?x<=6)
delete,On(?Obj,?src)
add,On(?Obj,?dest)
物体,Weight(A,4),Weight(B,1)
初始状态：
On(table,A),On(A,B)
目标状态：
On(B,A),On(table,B)
2009-8-20 史忠植 高级人工智能 30
任务分配规划结果如下：
Step1.Action=Move,Step1.Obj=B,Step1.dest=table,
Step2.Action=Joint-Move,Step2.Obj=A,Step2.dest=B,
Step1 < Step2
然后根据主体能力库，对动作步骤中的角色进行任务分配。
主体能力库如下：
agent1,CanDo Move as actor1
CanDo Joint-Move as actor1,actor2
agent2,CanDo Joint-Move as actor1,actor2
需要分配的角色：
Step1(Move).actor1,可选主体 {agent1}
Step2(Joint-Move).actor1,可选主体 {agent1,agent2}
Step2(Joint-Move).actor2,可选主体 {agent1,agent2}
2009-8-20 史忠植 高级人工智能 31
规划间的冲突规划间冲突分两种：
目标冲突：两个规划的目标冲突。
动作冲突：一个规划中的一个动作会破坏另一个规划中的一个动作的前提。
解决方法：
目标冲突：放弃一个不太重要的目标。
动作冲突：在动作之间添加时序约束。
2009-8-20 史忠植 高级人工智能 32
规划间冲突举例
A
B
B
初始状态 agent1目标状态
agent1 agent2 Agent３
C
A
C
A
C
agent3目标状态
2009-8-20 史忠植 高级人工智能 33
规划间冲突举例
agent1的目标,On(B,Table),On(A,B),On(C,A)
规划,Move(B,Table),Move(A,B),Move(C,A)
agent2的目标,On(C,A)
规划,Move(B,Table),Move(C,A)
当按照下面的顺序执行时,发生冲突：
Agent1,Move(B,Table)
Agent2,Move(C,A)
Agent1,Move(A,B)无法执行
2009-8-20 史忠植 高级人工智能 34
规划间冲突消解方法规划间冲突的消解方法也是添加约束,包括顺序约束和变量绑定约束,不过这些约束是在规划之间的约束 。
规划间的约束要靠多个主体的协调来实现 。
顺序约束：动作执行过程中添加同步动作
WaitFor和 Inform。
变量绑定约束：主体之间通信传递变量约束的更新 。
2009-8-20 史忠植 高级人工智能 35
冲突消解方法举例
agent1的规划：
Move(B,Table),Move(A,B),Move(C,A)
agent2的规划：
Move(B,Table),Move(C,A)
当按照下面的顺序执行时,发生冲突：
Agent1,Move(B,Table)
Agent2,Move(C,A)
Agent1,Move(A,B)无法执行消解方法：
升级：添加顺序约束 agent1.Move(A,B)<agent2.Move(C,A)
2009-8-20 史忠植 高级人工智能 36
约束一致性通过添加新约束的方法可以消解冲突，但是新约束可能会与原有的约束发生矛盾。
矛盾分为两种：
顺序约束不一致
变量绑定约束不一致
2009-8-20 史忠植 高级人工智能 37
顺序约束不一致顺序约束不一致 。 令 和 为两个顺序约束的集合,
与 在多个主体的规划中矛盾,当且仅当使得：
并且 。
例如,agent1.step1<agent2.step1
agent2.step1<agent1.step2
agent1.step2<agent1.step1
1R 2R
1R 2R SO,
)()( 1 OORTR )()( 2 OORTR
2009-8-20 史忠植 高级人工智能 38
变量绑定约束不一致令 和 为两个等价和不等价约束的集合 。 令 为
R中所有等价约束,为 R中所有不等价约束 。
与 在多个主体的规划中矛盾,当且仅当存在变量 x和 y
使得：
而且
。
例如,agent1.step1.dest=agent2.step1.obj
agent1.step1.dest=A
agent2.step1.obj=B
1R 2R )(RCo
)(RNonco
1R 2R
))()(()( 21 CoRCoRCoERyx
))()(()( 21 N o n coRN o n coRN o n coyx
2009-8-20 史忠植 高级人工智能 39
多主体规划的过程
1) 规划生成动作步骤
2) 检测规划间的冲突
3) 如果检测到冲突，则消解冲突
4) 添加约束消解冲突时，要进行约束一致性判断
5) 任务分配
2009-8-20 史忠植 高级人工智能 40
多主体规划的两种基本方式
集中式规划：由中央协调主体来进行规划，
然后将规划结果分配给各主体执行。缺点是当任务很多，或者很复杂时，中央协调主体的负担很重，成为系统的瓶颈。
分布式规划：每个主体自行进行规划，冲突的检测和消解通过主体间的协商解决。
缺点是冲突的检测和消解比较困难。
2009-8-20 史忠植 高级人工智能 41
新的研究方向
动态规划
条件规划
概率规划
不完备信息规划
