人工智能基础之自动规划系统

目录第一章绪论第二章知识表示

第三章搜索技术第四章推理技术第五章机器学习

第六章教授系统

第七章自动规划系统第八章自然语言了解第九章智能控制第十章人工智能程序设计人工智能基础之自动规划系统第1页7.1自动规划概述7.1.1规划概念及作用

1.规划概念

定义7.1

从某个特定问题状态出发，寻求一系列行为动作，并建立一个操作序列，直到求得目标状态为止。这个求解过程就称为规划。

定义7.2

规划是对某个待求解问题给出求解过程步骤。规划包括怎样将问题分解为若干对应子问题，以及怎样统计和处理问题求解过程中发觉各子问题间关系。

定义7.3

规划系统是一个包括相关问题求解过程步骤系统。如计算机或飞机设计、火车或汽车运输路径、财政和军事规划等问题。人工智能基础之自动规划系统第2页7.1自动规划概述7.1.1规划概念及作用例：救援仿真机器人系统（RoboCupRescueSimulationSystem，RCRSS）

①

消防智能体②

医疗智能体③

警察智能体④

普通市民⑤

中心智能体⑥

路障⑦

避难所⑧

着火建筑物⑨

普通建筑物）

人工智能基础之自动规划系统第3页7.1自动规划概述7.1.1规划概念及作用

2.规划作用规划可用来监控问题求解过程，并能够在造成较大危害之前发觉差错。规划好处可归纳为简化搜索、处理目标矛盾以及为差错赔偿提供基础。

“十二五”规划、城市规划、企业发展规划人工智能基础之自动规划系统第4页7.1自动规划概述7.1.2规划分类和问题分解路径

1.规划分类（1）按规划内容分国家、地方、重大项目、企业、交通、城市、环境…

（2）按规划方法分

非递阶（非分层）规划与递阶（分层）规划；线性规划与非线性规划；同时规划与异步规划；基于脚本、框架和本体规划；基于教授系统规划；基于竞争机制规划；…

（3）按规划实质分

任务规划、路径规划、轨迹规划…人工智能基础之自动规划系统第5页7.1自动规划概述7.1.2规划分类和问题分解路径

2.问题分解路径把一些较复杂问题分解为一些较小子问题。有两条实现这种分解主要路径。第一条主要路径是当从一个问题状态移动到下一个状态时，无需计算整个新状态，而只要考虑状态中可能改变了那些部分。第二条主要路径是把单一困难问题分割为几个有希望较为轻易处理子问题。人工智能基础之自动规划系统第6页7.1自动规划概述7.1.2规划分类和问题分解路径

3.域预测和规划修正

（1）域预测

问题论域预测。对于不可预测论域，考虑可能结果集合，按照它们出现可能性以某个次序排列。然后，产生一个规划、并试图去执行这个规划。

（2）规划修正

规划执行失败造成对规划修正。

在规划过程中不但要统计规划执行步骤，而且要统计每一步必须要执行理由。人工智能基础之自动规划系统第7页7.2基于谓词逻辑规划

用谓词逻辑来描述世界模型及规划过程。

世界模型谓词逻辑表示定义谓词确定问题初始状态确定问题目标状态确定基本操作

基于谓词逻辑规划基本过程问题分解子问题规划得到操作序列人工智能基础之自动规划系统第8页7.3STRIPS规划系统

7.3.1积木世界机器人规划BACCBA机械手机械手(a)(b)人工智能基础之自动规划系统第9页7.3STRIPS规划系统7.3.1积木世界机器人规划1.积木世界机器人问题机器人能够执行动作举比如下：unstack(a,b)：把堆放在积木b上积木a捡起。在进行这个动作之前，要求机器人手为空手，且积木a顶上是空。stack(a,b)：把积木a堆放在积木b上。动作之前要求机械手必须已抓住积木a，而且积木b顶上必须是空。pickup(a)：从桌面上捡起积木a，并抓住它不放。在动作之前要求机械手为空手，而且积木a顶上没有任何东西。putdown(a)：把积木a放置到桌面上。要求动作之前机械手已抓住积木a。人工智能基础之自动规划系统第10页7.3STRIPS规划系统

7.3.1积木世界机器人规划1.积木世界机器人问题

状态描述谓词：

ON(a,b)：积木a在积木b之上。

ONTABLE(a)：积木a在桌面上。

CLEAR(a)：积木a顶上没有任何东西。

HOLDING(a)：机械手正抓住积木a。

HANDEMPTY：机械手为空手。人工智能基础之自动规划系统第11页7.3STRIPS规划系统

7.3.1积木世界机器人规划2.用F规则求解规划序列采取F规则表示机器人动作，这是一个叫做STRIPS规划系统规则，它由3部分组成：第一部分是先决条件。为了使F规则能够应用到状态描述中去。第二部分是一个叫做删除表谓词。当一条规则被应用于某个状态描述或数据库时，就从该数据库删去删除表内容。第三部分叫做添加表。当把某条规则应用于某数据库时，就把该添加表内容添进该数据库。人工智能基础之自动规划系统第12页7.3STRIPS规划系统

7.3.1积木世界机器人规划2.用F规则求解规划序列例：

move(x,y,z):把物体x从物体y上面移到物体z上面。

先决条件：CLEAR(x),CLEAR(z),ON(x,y)

删除表：ON(x,y),CLEAR(z)添加表：ON(x,z),CLEAR(y)人工智能基础之自动规划系统第13页7.3STRIPS规划系统

7.3.2STRIPS规划系统

STanfordResearchInstituteProblemSolver——STRIPSSTRIPS系统组成以下：

(1)世界模型。为一阶谓词演算公式。

(2)操作符(F规则)。包含先决条件、删除表和添加表。

(3)操作方法。应用状态空间表示和中间-结局分析。规划过程每个STRIPS问题解答为某个实现目标操作符序列，即到达目标规划。

人工智能基础之自动规划系统第14页7.4分层规划探索规划时首先只考虑一层细节，然后再注意规划中比这一层低一层细节，所以把它叫做长度优先搜索。NOAH规划系统1.应用最小约束策略一个寻找非线性规划而无须考虑操作符序列全部排列方法是把最少约束策略应用来选择操作符执行次序问题。问题求解系统NOAH采取一个网络结构来统计它所选取操作符之间所需要排序。它也分层进行操作运算，即首先建立起规划抽象轮廓，然后在后续各步中，填入越来越多细节。人工智能基础之自动规划系统第15页7.4分层规划2.检验准则

准则法已被应用于各种规划生成系统。对于早期系统，如HACKER系统，准则只用于舍弃不满足规划。在NOAH系统中，准则被用来提出推定方法方便修正所产生规划。

第一个包括准则是归结矛盾准则。第二个准则叫做消除多出先决条件准则，包含除去对子目标多出说明。能够把分层规划和最少约定策略十分直接地结合起来，以求得非线性规划而不产生一个庞大搜索树。

人工智能基础之自动规划系统第16页7.5基于教授系统机器人规划1.系统结构及规划机理

（1）知识库：用于存放一些特定领域教授知识和经验，包含机器人工作环境世界模型、状态、物体描述等事实和可行操作或规则等。（2）

控制策略：包含综合机理，确定系统应该应用什么规则以及采取什么方式去寻找该规则。（3）

推理机：用于记忆所采取规则和控制策略及推理策略。（4）知识获取：首先获取某特定域教授知识。然后用程序设计语言把这些知识变换为计算机程序。最终把它们存入知识库待用。人工智能基础之自动规划系统第17页7.5基于教授系统机器人规划

(5)

解释与说明：经过用户接口，在教授系统与用户之间进行对话，从而使用户能够输入数据、提出问题、知道推理结果以及了解推理过程等。2.任务级机器人规划三要素（1）建立模型：世界模型。（2）任务说明：定义状态及状态变换次序。（3）程序综合。3.ROPES