本文共 7126 字，大约阅读时间需要 23 分钟。

人智导（二十一）：规划（上）

规划方法实现问题求解

规划方法构建智能体

• 问题求解：构建一个plan（动作序列），从初始状态达到目标状态
• 规划(planning)：推理方法实现问题求解过程
• 知识表示方法：
  • 状态(state)
  • 动作(action)
  • 目标(goal)
• 推理引擎
  • 自动发现达到目标的步骤(solution)

问题求解(Problem Solving)方法

程序框架

Function SIMPLE-PROBLEM-SOLVING-AGENT(p) returns an action	inputs: p            // a percept	static: s            // an action sequence, initially empty	        state        // some description of the current world state	        g            // a goal, initially null	        problem      // a problem formulation	state <--- UPDATE-STATE(state, p)	if s is empty then		g <--- FORMULATE-GOAL(state)		problem <--- FORMULATE-PROBLEM(state, g)		s <--- Search(problem)	action <--- FIRST(s)	s <--- REST(s)	return action

规划(Planning)方法

程序框架

Function SIMPLE-PLANNING-AGENT(percept) returns an action	static: KB              // a knowledge base (includes action description)	        p               // a plan, initially NoPlan	        t               // a counter, initially 0, indicating time	local variables: G      // a goal	                 current  // a current state description	TELL(KB, MAKE-PERCEPT-SENTENCE(percept, t))	current <--- STATE-DESCRIPTION(KB, t)	if p=NoPlan then		G <--- ASK(KB, MAKE-GOAL-QUERY(t))		p <--- PLANNER(current, G, KB)	if p=NoPlan or is empty then action <--- NoOp	else action <--- FIRST(p), p <--- REST(p)	TELL(KB, MAKE-ACTION-SENTENCE(action, t))	t <--- t+1	return action

规划方法的特点（与问题求解对比）

1. 更为open的问题表达方式，允许insight进行选择

• 规划方法采用逻辑（一阶谓词逻辑）作为表示语言
• 问题求解方法：高的分支因素导致高的计算代价（非目标驱动的搜索）

2. 发现的解决途径不须是全序动作序列

• solution无须是从初始状态开始的全序的链式序列
• 问题求解solution是全序的。这对于复杂的问题，发现solution过程往往无效率

3. 分治策略方式分解目标成一系列子目标

• 复杂的目标可以分解为相对简单的子目标分别实现
• 现实应用中有许多情况，同时有多个目标（合取组合的goals）

状态空间下的规划

• 状态空间模型：世界由一系列状态组成，当前状态通过动作转移到后继状态
• 一阶谓词逻辑表示状态，如 at(Agent, [1, 1], S_0)
• 状态转移后继函数Result(action, S_i) = S_j，如 Result(Forward, S_0) = S_1; Result(Turn(Right), S_1) = S_2; Result(Forward, S_2) = S_3
• 规划：动作导致状态变化 视为 逻辑推理问题

基于一阶谓词逻辑的规划

• 状态及动作的表示：
  • 初始状态：谓词逻辑句子表示，如$$At(Home,S_0)\wedge \neg Have(Milk,S_0)\wedge \neg Have(Bananas,S_0)\wedge \neg Have(Drill,S_0)$$
  • 目标状态：形如query句子询问合适的状态是什么， 如 $$\exists At(Home,s)\wedge Have(Milk,S)\wedge Have(Bananas,S)\wedge Have(Drill,S)$$
• 动作导致状态变化
  • Result(a, S) = S_1 a：单一动作
  • Result(I, S) = S_i I：动作序列
• 后继函数Result(I, S)的定义
  • $\forall SResult([],S)=S$
  • $\forall SResult([a|p],S)=Result(p,Result(a,S))$
• 一个plan（动作序列）p应用到初始状态S_0，并产生一个满足目标的状态，如$$At(Home,Result(p,S_0))\wedge Have(Milk,Result(p,S_0))\wedge Have(Bananas,Result(p,S_0))\wedge Have(Drill,Result(p,S_0))$$ $$Have(Bananas,Result(p,S_0))\wedge Have(Drill,Result(p,S_0))$$
• 针对query（目标）：$$\exists At(Home,S)\wedge Have(Milk,S)\wedge Have(Bananas,S)\wedge Have(Drill,S)$$得到如下动作序列plan(solution)：$$p=[Go(Supermarket),Buy(Milk),Buy(Banana),Go(HardwareStore),Buy(Drill),Go(Home)]$$

实用的规划方法与规划空间

实用的规划方法

• 好的理论不能保证好的实用性
• 无指导逻辑推理下的规划仍是低效率的
• goal $\to$ planner 面向的是特定任务，有别于通用意义的query $\to$ prover
• 如何使得规划程序实用有效：
  • 针对问题的求解，限制表示语言的规模和范围
  • 使用面向特殊目的的算法，替代通用目的推理引擎搜索产生plan

规划方法中的表示问题

• 设计一个规划器(planner)：限定的逻辑表示更有效于通用目的的推理引擎
• 限定的逻辑语言：规划域定义语言(Planning Domain Definition Language)
  • 典型地，STRIPS-style
  • 保留逻辑表示语言的表达能力
  • 提高规划算法效率

STRIPS语言的表示

动作(action)表示，包括了三部分：

• 动作描述：命名
• 前提条件：原子句的合取
• 动作效果：文字的合取
  举例：
  $$\begin{gathered} Op(ACTION:Go(there), \\ PRECOND:At(here)\wedge Path(here,there), \\ EFFECT:At(there)\wedge \neg At(here)) \end{gathered}$$

动作的表示

• 动作的定义可以包括变量：非单一动作而是描述一个动作集，所用变量都是全称变量
• 前提条件(preconditions)和动作效果(effects)的表示被约束限制
• 一个动作o在状态s情况下是可出发的，如果Precond(o)$\subset$s

在状态空间中的规划

• 问题求解过程中的搜索基于状态空间
  • 前向式planner：前向推理，从初始状态到目标状态（通过空间中可能的状态）
  • 后向式planner：后向推理，从目标状态到初始状态（能减少分支因子）

规划空间的概念

• 规划空间(space of plans)：一种有效的替代方法
• 规划空间（部分规划pertial plan）
  • 从简单的、不完整的规划(partial plan)开始
  • 然后扩展这个不完整规划(partial plan)，直至获得一个完整规划(complete plan)，以求解问题

规划空间(Plan Space)的表示

• 针对部分规划(partial plans)的操作
  • 增加一个步骤/动作(add a step)：满足一个开放条件
  • 增加一个连接(add a link)：从一个存在的动作到开放条件(open condition)
  • 排序一个步骤/动作(order one step)：确定与其它已有步骤的次序
• 开放条件(open condition)：一个步骤/动作中的尚未满足的前提条件
  • 逐步地从不完整规划过渡到完整的规划(complete plans)
  • 解决方案(solution)即为最终的规划plan

规划(plan)的表示

规划plan：被定义为包括如下四个部分：

• 一个步骤(step)集合 每个步骤是问题求解过程中的一个动作
• 一个步骤次序约束(order constraint)的集合，形如$S_i<S_j$（其中步骤$S_i$必须发生在步骤$S_j$之前）
• 一个变量置换的集合表，形如v=x
• 一个步骤之间因果关联(causal links)的集合，形如$S_i\to S_j$步骤$S_j$能够满足步骤$S_j$的前提条件

举例：Shoes-and-Socks问题

• 目标：RightShoeOn$\wedge$LeftShoeOn
• 初始状态：空（没有任何文字literals)
• 步骤/动作：
  $$Op(ACTION:RightShoe,PRECOND:RightSockOn,EFFECT:RightShoeOn)$$
  $$Op(ACTION:RightSock,EFFECT:RightSockOn)$$
  $$Op(ACTION:LeftShoe,PRECOND:LeftSockOn,EFFECT:LeftShoeOn)$$
  $$Op(ACTION:LeftSock,EFFECT:LeftSockOn)$$
• 初始的部分规划:
  plan(Step:{S_1: Op(ACTION:Start), S_2:Op(ACTION:Finish, PRECOND:RightShoeOn$\wedge$LeftShoeOn)}.
  Orderings:{S_1 < S_2}
  Bindings:{}
  Links:{})
  开始的步骤S_1(Start)：没有前提条件，动作效果：初始状态true
  结束的步骤S_2(Finish)：前提条件是目标状态，没有动作效果项

问题求解Solution的定义

• 早期定义Solution：一个动作序列，智能体保证能通过该序列的执行达到目标
• 有两方面局限：
  • 客观世界中，部分有序的plan是更自然的
  • 组合子规划(sub-plans)，以完成更复杂的问题（并行性）
• 求解solutions的新定义（基于部分有序的规划）
  求解solution，是一个同时满足完整性和一致性的规划plan
  • 完整性(Completeness):
    • 每个步骤的每个前提条件都可被其它步骤达到/满足；
    • 前提条件是可达到/满足的，当且仅当它是某一步骤的动作结果，并不被其它步骤所干涉
  • 一致性(Consistency):
    • 在次序约束或变量置上没有矛盾现象

转载地址：http://trzai.baihongyu.com/