人工智能基础07--自动规划系统精编版

《人工智能基础07--自动规划系统精编版》由会员分享，可在线阅读，更多相关《人工智能基础07--自动规划系统精编版（49页珍藏版）》请在金锄头文库上搜索。

1、目录,第一章绪论 第二章知识表示 第三章搜索技术 第四章推理技术 第五章机器学习 第六章专家系统 第七章自动规划系统 第八章 自然语言理解 第九章 智能控制 第十章 人工智能程序设计,自动规划概述 基于谓词逻辑的规划 STRIPS规划系统 分层规划 基于专家系统的机器人规划 轨迹规划简介,7.1 自动规划概述,7.1.1 规划的概念及作用 1. 规划的概念 定义7.1 从某个特定的问题状态出发，寻求一系列行为动作，并建立一个操作序列，直到求得目标状态为止。这个求解过程就称为规划。 定义7.2 规划是对某个待求解问题给出求解过程的步骤。规划涉及如何将问题分解为若干相应的子问题，以及如何记录和处理

2、问题求解过程中发现的各子问题间的关系。 定义7.3 规划系统是一个涉及有关问题求解过程步骤的系统。如计算机或飞机设计、火车或汽车运输路径、财政和军事规划等问题。,7.1 自动规划概述,7.1.1 规划的概念及作用 例： 救援仿真机器人系统 （RoboCup Rescue Simulation System，RCRSS） 消防智能体 医疗智能体 警察智能体 普通市民 中心智能体 路障 避难所 着火建筑物 普通建筑物）,7.1 自动规划概述,7.1.1 规划的概念及作用 2. 规划的作用 规划可用来监控问题求解过程，并能够在造成较大的危害之前发现差错。规划的好处可归纳为简化搜索、解决目标矛盾以及为

3、差错补偿提供基础。 “十二五”规划、城市规划、企业发展规划,7.1 自动规划概述,7.1.2 规划的分类和问题分解途径 1. 规划的分类 （1）按规划内容分 国家、地方、重大项目、企业、交通、城市、环境 （2）按规划方法分 非递阶（非分层）规划与递阶（分层）规划；线性规划与非线性规划；同步规划与异步规划；基于脚本、框架和本体的规划；基于专家系统的规划；基于竞争机制的规划； （3）按规划实质分 任务规划、路径规划、轨迹规划,7.1 自动规划概述,7.1.2 规划的分类和问题分解途径 2. 问题分解途径 把某些较复杂的问题分解为一些较小的子问题。有两条实现这种分解的重要途径。 第一条重要途径是当从

4、一个问题状态移动到下一个状态时，无需计算整个新的状态，而只要考虑状态中可能变化了的那些部分。 第二条重要途径是把单一的困难问题分割为几个有希望的较为容易解决的子问题。,7.1 自动规划概述,7.1.2 规划的分类和问题分解途径 3. 域的预测和规划的修正 （1）域的预测 问题论域的预测。对于不可预测的论域，考虑可能的结果集合，按照它们出现的可能性以某个次序排列。然后，产生一个规划、并试图去执行这个规划。 （2）规划的修正 规划执行失败导致对规划的修正。 在规划过程中不仅要记录规划的执行步骤，而且要记录每一步必须要执行的理由。,7.2 基于谓词逻辑的规划,用谓词逻辑来描述世界模型及规划过程。 世

5、界模型的谓词逻辑表示 定义谓词 确定问题初始状态 确定问题目标状态 确定基本操作 基于谓词逻辑规划的基本过程 问题分解 子问题规划 得到操作序列,7.3 STRIPS规划系统,7.3.1 积木世界的机器人规划 求解机器人完成规定工作的动作序列,B,A,C,C,B,A,机械手,机械手,(a),(b),7.3 STRIPS规划系统,7.3.1 积木世界的机器人规划 1. 积木世界的机器人问题 机器人能够执行的动作举例如下： unstack(a,b)：把堆放在积木b上的积木a拾起。在进行这个动作之前，要求机器人的手为空手，且积木a的顶上是空的。 stack(a,b)： 把积木a堆放在积木b上。动作之

6、前要求机械手必须已抓住积木a，而且积木b顶上必须是空的。 pickup(a)： 从桌面上拾起积木a，并抓住它不放。在动作之前要求机械手为空手，而且积木a顶上没有任何东西。 putdown(a)： 把积木a放置到桌面上。要求动作之前机械手已抓住积木a。,7.3 STRIPS规划系统,7.3.1 积木世界的机器人规划 1. 积木世界的机器人问题 状态描述谓词： ON(a,b)： 积木a在积木b之上。 ONTABLE(a)： 积木a在桌面上。 CLEAR(a)： 积木a顶上没有任何东西。 HOLDING(a)： 机械手正抓住积木a。 HANDEMPTY： 机械手为空手。,7.3 STRIPS规划系统

7、,7.3.1 积木世界的机器人规划 2.用F规则求解规划序列 采用F规则表示机器人的动作，这是一个叫做STRIPS规划系统的规则，它由3部分组成： 第一部分是先决条件。为了使F规则能够应用到状态描述中去。 第二部分是一个叫做删除表的谓词。当一条规则被应用于某个状态描述或数据库时，就从该数据库删去删除表的内容。 第三部分叫做添加表。当把某条规则应用于某数据库时，就把该添加表的内容添进该数据库。,7.3 STRIPS规划系统,7.3.1 积木世界的机器人规划 2.用F规则求解规划序列 例： move(x, y, z): 把物体x从物体y上面移到物体z上面。 先决条件：CLEAR(x), CLEAR

8、(z), ON(x,y) 删除表：ON(x, y), CLEAR(z) 添加表：ON(x, z), CLEAR(y),7.3 STRIPS规划系统,7.3.2 STRIPS规划系统 斯坦福大学人工智能研究所于1966-72年研制的Shakey机器人是第一台能够进行行动推理的多用移动机器人，该项目融合了机器人视觉、机器人学和自动推理研究成果。机器人的任务是在一些相连的房间里，将用户指定的箱子推到指定的位置。对于用户输入的每一个任务，Shakey自主地规划完成该任务的行动并依次执行。 Shakey项目技术：规划语言STRIPS（ STanford Research Institute Proble

9、m SolverSTRIPS ）和A*算法等。 STRIPS语言用来描述外部世界模型并支持任务规划，它提供了框架问题的一种简洁、高效的解法，但理论上并不完备。,7.3 STRIPS规划系统,7.3.2 STRIPS规划系统 STRIPS系统的组成如下： (1) 世界模型。为一阶谓词演算公式。 (2) 操作符(F规则)。包括先决条件、删除表和添加表。 (3) 操作方法。应用状态空间表示和中间-结局分析。 规划过程 每个STRIPS问题的解答为某个实现目标的操作符序列，即达到目标的规划。,A Service Robot Copes with Changes Understanding, Learn

10、ing, Planning, and Acting,7.4 分层规划,探索规划时首先只考虑一层的细节，然后再注意规划中比这一层低一层的细节，所以把它叫做长度优先搜索。 NOAH规划系统 1. 应用最小约束策略 一个寻找非线性规划而不必考虑操作符序列的所有排列的方法是把最少约束策略应用来选择操作符执行次序的问题。 问题求解系统NOAH采用一种网络结构来记录它所选取的操作符之间所需要的排序。它也分层进行操作运算，即首先建立起规划的抽象轮廓，然后在后续的各步中，填入越来越多的细节。,7.4 分层规划,2. 检验准则 准则法已被应用于各种规划生成系统。对于早期的系统，如HACKER系统，准则只用于舍弃

11、不满足的规划。在NOAH系统中，准则被用来提出推定的方法以便修正所产生的规划。第一个涉及的准则是归结矛盾准则。 第二个准则叫做消除多余先决条件准则，包括除去对子目标的多余说明。 可以把分层规划和最少约束策略十分直接地结合起来，以求得非线性规划而不产生一个庞大的搜索树。,7.5 基于专家系统的机器人规划,1. 系统结构及规划机理 （1）知识库：用于存储某些特定领域的专家知识和经验，包括机器人工作环境的世界模型、状态、物体描述等事实和可行操作或规则等。 （2） 控制策略：包含综合机理，确定系统应当应用什么规则以及采取什么方式去寻找该规则。 （3） 推理机：用于记忆所采用的规则和控制策略及推理策略。

12、 （4）知识获取：首先获取某特定域的专家知识。然后用程序设计语言把这些知识变换为计算机程序。最后把它们存入知识库待用。,7.5 基于专家系统的机器人规划,(5)解释与说明：通过用户接口，在专家系统与用户之间进行对话，从而使用户能够输入数据、提出问题、知道推理结果以及了解推理过程等。 2. 任务级机器人规划三要素 （1）建立模型：世界模型。 （2）任务说明：定义状态及状态变换次序。 （3）程序综合。 3. ROPES机器人规划系统,7.6 轨迹规划简介,轨迹：机械手在运动过程中的位移、速度和加速度。 轨迹规划：根据任务的要求，计算出预期的轨迹。 在机械手运动学和动力学基础上，讨论在关节空间和笛卡

13、尔空间中机器人运动的轨迹规划和轨迹生成方法,7.6 轨迹规划简介,例：NAO机器人检球动作。,地球上的生物物种在漫长的过程中形成了丰富的行为特性，并且一直不断地完善和发展，以更好地适应其所生存的环境。生物群体和自然生态系统可以通过自身的演化就能使许多在人类看起来高度复杂的优化问题得到完美解决。因此，各种模仿生物群体的智能仿生算法被相继提出，得到了深入研究和应用实践。 群智能思想的产生主要源于复杂适应系统理论以及人工生命的研究。,群智能算法群智能思想起源,群智能算法群智能思想起源,复杂适应系统( Complex Adaptive System, CAS) 理论：1994 年由 Holland 教

14、授正式提出。CAS中成员称为具有适应性的主体, 简称主体。 主体的适应性, 是指它能够与环境以及其它主体进行交流，在交流的过程中 “学习” 或 “积累经验”，并且根据学到的经验改变自身的结构和行为方式。CAS具有四个基本特点: （1）首先, 主体是主动的、活的实体。具有适应性的主体的概念把个体主动性提高到了系统进化基本动因的位置, 从而成为研究与考察宏观行为的出发点。 （2）其次, 个体与环境(包括个体之间)之间的相互影响、相互作用是系统演变和进化的主要动力。相互作用是“可记忆”的, 它表现为进化过程中每个个体的结构和行为方式的变化，以不同的方式 “存储” 在个体内部。,群智能算法群智能思想起

15、源,（3）再次, 这种方法不像许多其他的方法那样, 把宏观和微观截然分开, 而是把它们有机地联系起来。 （4）最后, 这种建模方法还引进了随机因素的作用, 使它具有更强的描述和表达能力。随机因素的影响不仅影响状态, 而且影响组织结构和行为方式。具有主动性的个体会接受教训,总结经验, 并且以某种方式把 “经历” 记住, 使之 “固化” 在自己以后的行为方式中。 CAS理论提供了模拟生物、 生态、 经济、 社会等复杂系统的巨大潜力。,群智能算法群智能思想起源,人工生命(Artificial Life, AL)是用来研究具有某些生命基本特征的人工系统。 近年来, 人工生命的研究发展非常快, 在某些方

16、面的研究已与传统的生物科学形成了互补。人工生命包括两方面的内容: 如何利用计算技术研究生物现象; 如何利用生物技术研究计算问题。 第二部分的内容的研究中，现已经有了很多源于生物现象的计算技巧，例如，人工神经网络是简化的大脑模型，遗传算法是模拟基因进化的过程，目前这一类计算技术被统称为自然计算。群智能属于自然计算中的一类，它模拟另一种生物系统：社会系统，更确切地说，是模拟由简单个体组成的群落与环境以及个体之间的互动行为，这些模拟系统利用局部信息从而可能产生不可预测的群体行为。,群智能算法群智能思想起源,群智能( Swarm Intelligence, SI)： 1992年由 Beni, Hack-wood 和 Wang在分子自动机系统中提出。 1999 年, Bonabeau, Dorigo 和 Theraulaz 在 Swarm Intel-ligence: From Natural to Artificial Systems中对群智能进行