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

合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室1/20目录o第一章第一章绪论o第二章第二章知知识表示表示 o第三章搜索技第三章搜索技术o第四章推理技第四章推理技术o第五章机器学第五章机器学习 o第六章第六章专家系家系统o第七章自第七章自动规划系划系统o第八章第八章自然自然语言理解言理解o第九章第九章智能控制智能控制o第十章第十章人工智能程序人工智能程序设计合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室2/207.1 自动规划概述7.1.1规划的概念及作用划的概念及作用1.规划的概念划的概念定定义7.1从某个特定的从某个特定的问题状状态出出发，寻求一系列行求一系列行为动作，并建立一个操作序列，直到求得目作，并建立一个操作序列，直到求得目标状状态为止。止。这个求解个求解过程就称程就称为规划划。定定义7.2规划是划是对某个待求解某个待求解问题给出求解出求解过程的步程的步骤。规划涉及如何将划涉及如何将问题分解分解为若干相若干相应的子的子问题，以及如何，以及如何记录和和处理理问题求解求解过程中程中发现的各子的各子问题间的关系。的关系。定定义7.3规划系划系统是一个涉及有关是一个涉及有关问题求解求解过程步程步骤的系的系统。如。如计算机或算机或飞机机设计、火、火车或汽或汽车运运输路径、路径、财政和政和军事事规划等划等问题。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室3/207.1 自动规划概述7.1.1规划的概念及作用划的概念及作用例：例：救援仿真机器人系救援仿真机器人系统（RoboCupRescueSimulationSystem，RCRSS）消防智能体消防智能体医医疗智能体智能体警察智能体警察智能体普通市民普通市民中心智能体中心智能体路障路障避避难所所着火建筑物着火建筑物普通建筑物）普通建筑物）合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室4/207.1 自动规划概述7.1.1规划的概念及作用划的概念及作用2.规划的作用划的作用规划可用来划可用来监控控问题求解求解过程，并能程，并能够在造成在造成较大的危害大的危害之前之前发现差差错。规划的好划的好处可可归纳为简化搜索、解决目化搜索、解决目标矛盾矛盾以及以及为差差错补偿提供基提供基础。“十二五十二五”规划、城市划、城市规划、企划、企业发展展规划划合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室5/207.1 自动规划概述7.1.2规划的分划的分类和和问题分解途径分解途径1.规划的分划的分类（1）按）按规划内容分划内容分国家、地方、重大国家、地方、重大项目、企目、企业、交通、城市、交通、城市、环境境（2）按）按规划方法分划方法分非非递阶（非分（非分层）规划与划与递阶（分（分层）规划；划；线性性规划与划与非非线性性规划；同步划；同步规划与异步划与异步规划；基于脚本、框架和本体的划；基于脚本、框架和本体的规划；基于划；基于专家系家系统的的规划；基于划；基于竞争机制的争机制的规划；划；（3）按）按规划划实质分分任任务规划、路径划、路径规划、划、轨迹迹规划划合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室6/207.1 自动规划概述7.1.2规划的分划的分类和和问题分解途径分解途径2.问题分解途径分解途径把某些把某些较复复杂的的问题分解分解为一些一些较小的子小的子问题。有两条。有两条实现这种分解的重要途径。种分解的重要途径。第一条重要途径是当从一个第一条重要途径是当从一个问题状状态移移动到下一个状到下一个状态时，无需无需计算整个新的状算整个新的状态，而只要考，而只要考虑状状态中可能中可能变化了的那些化了的那些部分。部分。第二条重要途径是把第二条重要途径是把单一的困一的困难问题分割分割为几个有希望的几个有希望的较为容易解决的子容易解决的子问题。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室7/207.1 自动规划概述7.1.2规划的分划的分类和和问题分解途径分解途径3.域的域的预测和和规划的修正划的修正（1）域的）域的预测问题论域的域的预测。对于不可于不可预测的的论域，考域，考虑可能的可能的结果果集合，按照它集合，按照它们出出现的可能性以某个次序排列。然后，的可能性以某个次序排列。然后，产生一生一个个规划、并划、并试图去去执行行这个个规划。划。（2）规划的修正划的修正规划划执行失行失败导致致对规划的修正。划的修正。在在规划划过程中不程中不仅要要记录规划的划的执行步行步骤，而且要，而且要记录每每一步必一步必须要要执行的理由。行的理由。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室8/207.2 基于谓词逻辑的规划用用谓词逻辑来描述世界模型及来描述世界模型及规划划过程。程。o世界模型的世界模型的谓词逻辑表示表示n定定义谓词n确定确定问题初始状初始状态n确定确定问题目目标状状态n确定基本操作确定基本操作o基于基于谓词逻辑规划的基本划的基本过程程n问题分解分解n子子问题规划划n得到操作序列得到操作序列合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室9/207.3 STRIPS规划系统7.3.1积木世界的机器人木世界的机器人规划划BACCBA机械手机械手机械手机械手(a)(b)合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室10/207.3 STRIPS规划系统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。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室11/207.3 STRIPS规划系统7.3.1积木世界的机器人木世界的机器人规划划1.积木世界的机器人木世界的机器人问题状状态描述描述谓词：ON(a,b)：积木木a在在积木木b之上。之上。ONTABLE(a)：积木木a在桌面上。在桌面上。CLEAR(a)：积木木a顶上没有任何上没有任何东西。西。HOLDING(a)：机械手正抓住机械手正抓住积木木a。HANDEMPTY：机械手机械手为空手。空手。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室12/207.3 STRIPS规划系统7.3.1积木世界的机器人木世界的机器人规划划2.用用F规则求解求解规划序列划序列采用采用F规则表示机器人的表示机器人的动作，作，这是一个叫做是一个叫做STRIPS规划划系系统的的规则，它由，它由3部分部分组成：成：第一部分是先决条件。第一部分是先决条件。为了使了使F规则能能够应用到状用到状态描述描述中去。中去。第二部分是一个叫做第二部分是一个叫做删除表的除表的谓词。当一条。当一条规则被被应用于用于某个状某个状态描述或数据描述或数据库时，就从，就从该数据数据库删去去删除表的内容。除表的内容。第三部分叫做添加表。当把某条第三部分叫做添加表。当把某条规则应用于某数据用于某数据库时，就把就把该添加表的内容添添加表的内容添进该数据数据库。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室13/207.3 STRIPS规划系统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)合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室14/207.3 STRIPS规划系统7.3.2STRIPS规划系划系统STanfordResearchInstituteProblemSolverSTRIPSSTRIPS系系统的的组成如下：成如下：(1)世界模型。世界模型。为一一阶谓词演算公式。演算公式。(2)操作符操作符(F规则)。包括先决条件、。包括先决条件、删除表和添加表。除表和添加表。(3)操作方法。操作方法。应用状用状态空空间表示和中表示和中间-结局分析。局分析。规划划过程程每个每个STRIPS问题的解答的解答为某个某个实现目目标的操作符序列，的操作符序列，即达到目即达到目标的的规划。划。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室15/207.4 分层规划探索探索规划划时首先只考首先只考虑一一层的的细节，然后再注意，然后再注意规划中比划中比这一一层低一低一层的的细节，所以把它叫做，所以把它叫做长度度优先搜索。先搜索。NOAH规划系划系统1.应用最小用最小约束策略束策略一个一个寻找非找非线性性规划而不必考划而不必考虑操作符序列的所有排列的操作符序列的所有排列的方法是把最少方法是把最少约束策略束策略应用来用来选择操作符操作符执行次序的行次序的问题。问题求解系求解系统NOAH采用一种网采用一种网络结构来构来记录它所它所选取的取的操作符之操作符之间所需要的排序。它也分所需要的排序。它也分层进行操作运算，即首先建行操作运算，即首先建立起立起规划的抽象划的抽象轮廓，然后在后廓，然后在后续的各步中，填入越来越多的的各步中，填入越来越多的细节。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室16/207.4 分层规划2.检验准准则准准则法已被法已被应用于各种用于各种规划生成系划生成系统。对于早期的系于早期的系统，如如HACKER系系统，准，准则只用于舍弃不只用于舍弃不满足的足的规划。在划。在NOAH系系统中，准中，准则被用来提出推定的方法以便修正所被用来提出推定的方法以便修正所产生的生的规划。划。第一个涉及的准第一个涉及的准则是是归结矛盾准矛盾准则。第二个准第二个准则叫做消除多余先决条件准叫做消除多余先决条件准则，包括除去，包括除去对子目子目标的多余的多余说明。明。可以把分可以把分层规划和最少划和最少约定策略十分直接地定策略十分直接地结合起来，以合起来，以求得非求得非线性性规划而不划而不产生一个生一个庞大的搜索大的搜索树。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室17/207.5 基于专家系统的机器人规划1.系系统结构及构及规划机理划机理（1）知）知识库：用于存：用于存储某些特定某些特定领域的域的专家知家知识和和经验，包括机器人工作包括机器人工作环境的世界模型、状境的世界模型、状态、物体描述等事、物体描述等事实和可和可行操作或行操作或规则等。等。（2）控制策略：包含控制策略：包含综合机理，确定系合机理，确定系统应当当应用什么用什么规则以及采取什么方式去以及采取什么方式去寻找找该规则。（3）推理机：用于推理机：用于记忆所采用的所采用的规则和控制策略及推理和控制策略及推理策略。策略。（4）知）知识获取：首先取：首先获取某特定域的取某特定域的专家知家知识。然后用。然后用程序程序设计语言把言把这些知些知识变换为计算机程序。最后把它算机程序。最后把它们存入存入知知识库待用。待用。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室18/207.5 基于专家系统的机器人规划(5)解解释与与说明：通明：通过用用户接口，在接口，在专家系家系统与用与用户之之间进行行对话，从而使用，从而使用户能能够输入数据、提出入数据、提出问题、知道推理、知道推理结果以及了解推理果以及了解推理过程等。程等。2.任任务级机器人机器人规划三要素划三要素（1）建立模型：世界模型。）建立模型：世界模型。（2）任）任务说明：定明：定义状状态及状及状态变换次序。次序。（3）程序）程序综合。合。3.ROPES机器人机器人规划系划系统合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室19/207.6 轨迹规划简介 轨迹：机械手在运迹：机械手在运动过程中的位移、速度和加速度。程中的位移、速度和加速度。轨迹迹规划：根据任划：根据任务的要求，的要求，计算出算出预期的期的轨迹。迹。在机械手运在机械手运动学和学和动力学基力学基础上，上，讨论在关在关节空空间和笛卡和笛卡尔空空间中机器人运中机器人运动的的轨迹迹规划和划和轨迹生成方法迹生成方法合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室20/207.6 轨迹规划简介 例：例：NAO机器人机器人检球球动作。作。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室21/20演讲完毕，谢谢观看！