人工智能自动规划.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,a单击此处编辑母版文本样式,a第二级,a第三级,a第四级,a第五级,*,合肥工业大学 人工智能与数据挖掘研究室,*,/20,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,目录,第,八,章自动,规划,课程：人工智能,专业：物流工程,人工智能自动规划,第1页,8,.1 自动规划概述,8,.1.1 规划概念及作用,1.规划概念,定义,8,.1,从某个特定问题状态出发，寻求一系列行为动作，并建立一个操作序列，直到求得目标状态为止。这个求解过程就称为,规划,。,定义,8,.2,规划是对某个待求解问题给出求解过程步骤。规划包括怎样将问题分解为若干对应子问题，以及怎样统计和处理问题求解过程中发觉各子问题间关系。,定义,8,.3,规划系统是一个包括相关问题求解过程步骤系统。如计算机或飞机设计、火车或汽车运输路径、财政和军事规划等问题。,人工智能自动规划,第2页,8,.1 自动规划概述,8,.1.1 规划概念及作用,例：,救援仿真机器人系统,（RoboCup Rescue Simulation System，RCRSS）,消防智能体,医疗智能体,警察智能体,普通市民,中心智能体,路障,避难所,着火建筑物,普通建筑物）,人工智能自动规划,第3页,8,.1 自动规划概述,8,.1.1 规划概念及作用,2.规划作用,规划可用来监控问题求解过程，并能够在造成较大危害之前发觉差错。规划好处可归纳为简化搜索、处理目标矛盾以及为差错赔偿提供基础。,“十二五”规划、城市规划、企业发展规划,人工智能自动规划,第4页,8,.1 自动规划概述,8,.1.2 规划分类和问题分解路径,1.规划分类,（1）按规划内容分,国家、地方、重大项目、企业、交通、城市、环境,（2）按规划方法分,非递阶（非分层）规划与递阶（分层）规划；线性规划与非线性规划；同时规划与异步规划；基于脚本、框架和本体规划；基于教授系统规划；基于竞争机制规划；,（3）按规划实质分,任务规划、路径规划、轨迹规划,人工智能自动规划,第5页,8,.1 自动规划概述,8,.1.2 规划分类和问题分解路径,2.问题分解路径,把一些较复杂问题分解为一些较小子问题。有两条实现这种分解主要路径。,第一条主要路径是当从一个问题状态移动到下一个状态时，无需计算整个新状态，而只要考虑状态中可能改变了那些部分。,第二条主要路径是把单一困难问题分割为几个有希望较为轻易处理子问题。,人工智能自动规划,第6页,8,.1 自动规划概述,8,.1.2 规划分类和问题分解路径,3.域预测和规划修正,（1）域预测,问题论域预测。对于不可预测论域，考虑可能结果集合，按照它们出现可能性以某个次序排列。然后，产生一个规划、并试图去执行这个规划。,（2）规划修正,规划执行失败造成对规划修正。,在规划过程中不但要统计规划执行步骤，而且要统计每一步必须要执行理由。,人工智能自动规划,第7页,8,.1 自动规划概述,8.1.3,执行规划系统任务普通方法,（1）选择和应用标准,（2）检验解答与空端,（3）修正殆正确解,人工智能自动规划,第8页,8.2任务规划,8.2,.1,积木世界机器人规划,B,A,C,C,B,A,机械手,机械手,(a),(b),人工智能自动规划,第9页,8.2,任务规划,8.2.1 积木世界机器人规划,1.积木世界机器人问题,机器人能够执行动作举比如下：,unstack(a,b)：把堆放在积木b上积木a捡起。在进行这个动作之前，要求机器人手为空手，且积木a顶上是空。,stack(a,b)：把积木a堆放在积木b上。动作之前要求机械手必须已抓住积木a，而且积木b顶上必须是空。,pickup(a)：从桌面上捡起积木a，并抓住它不放。在动作之前要求机械手为空手，而且积木a顶上没有任何东西。,putdown(a)：把积木a放置到桌面上。要求动作之前机械手已抓住积木a。,人工智能自动规划,第10页,8.2任务规划,8.2.1,积木世界机器人规划,1.积木世界机器人问题,状态描述谓词,：,ON(a,b)：积木a在积木b之上。,ONTABLE(a)：积木a在桌面上。,CLEAR(a)：积木a顶上没有任何东西。,HOLDING(a)：机械手正抓住积木a。,HANDEMPTY：机械手为空手。,人工智能自动规划,第11页,8.2任务规划,8.2.1,积木世界机器人规划,2.用F规则求解规划序列,采取F规则表示机器人动作，这是一个叫做STRIPS规划系统规则，它由3部分组成：,第一部分是先决条件。为了使F规则能够应用到状态描述中去。,第二部分是一个叫做删除表谓词。当一条规则被应用于某个状态描述或数据库时，就从该数据库删去删除表内容。,第三部分叫做添加表。当把某条规则应用于某数据库时，就把该添加表内容添进该数据库。,人工智能自动规划,第12页,8.2任务规划,8.2.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页,8.2任务规划,8.2.2,STRIPS规划系统,STanford Research Institute Problem SolverSTRIPS,STRIPS系统组成以下：,(1)世界模型。为一阶谓词演算公式。,(2)操作符(F规则)。包含先决条件、删除表和添加表。,(3)操作方法。应用状态空间表示和中间-结局分析。,规划过程,每个STRIPS问题解答为某个实现目标操作符序列，即到达目标规划。,人工智能自动规划,第14页,8.2任务规划,8.2.3 含有学习能力规划系统,1.PULP-I结构与操作方式,PULP-I 机器人规划系统是一个含有学习能力系统，它采取管理式学习，其作用原理是建立在类比基础上。,2.PULP-I世界模型和规划结果,PULP-I系统能够完成一系列规划任务。含有学习能力机器人问题求解与规划系统PULP-I已经成功地显示出规划性能改进。,人工智能自动规划,第15页,8.2任务规划,8.2.4 分层规划,1.,长度优先搜索,探索规划时首先只考虑一层细节，然后再注意规划中比这一层低一层细节，,2.,NOAH规划系统,（,1,）,.应用最小约束策略,一个寻找非线性规划而无须考虑操作符序列全部排列方法是把最少约束策略应用来选择操作符执行次序问题。,问题求解系统NOAH采取一个网络结构来统计它所选取操作符之间所需要排序。它也分层进行操作运算，即首先建立起规划抽象轮廓，然后在后续各步中，填入越来越多细节。,人工智能自动规划,第16页,8.2任务规划,（,2,）,.检验准则,准则法已被应用于各种规划生成系统。对于早期系统，如HACKER系统，准则只用于舍弃不满足规划。在NOAH系统中，准则被用来提出推定方法方便修正所产生规划。第一个包括准则是归结矛盾准则。,第二个准则叫做消除多出先决条件准则，包含除去对子目标多出说明。,能够把分层规划和最少约定策略十分直接地结合起来，以求得非线性规划而不产生一个庞大搜索树。,人工智能自动规划,第17页,8.2任务规划,8.2.5 基于教授系统机器人规划,1.系统结构及规划机理,（1）知识库：用于存放一些特定领域教授知识和经验，包含机器人工作环境世界模型、状态、物体描述等事实和可行操作或规则等。,（2）控制策略：包含综合机理，确定系统应该应用什么规则以及采取什么方式去寻找该规则。,（3）推理机：用于记忆所采取规则和控制策略及推理策略。,（4）知识获取：首先获取某特定域教授知识。然后用程序设计语言把这些知识变换为计算机程序。最终把它们存入知识库待用。,人工智能自动规划,第18页,8.2任务规划,(5)解释与说明：经过用户接口，在教授系统与用户之间进行对话，从而使用户能够输入数据、提出问题、知道推理结果以及了解推理过程等。,2.任务级机器人规划三要素,（1）建立模型：世界模型。,（2）任务说明：定义状态及状态变换次序。,（3）程序综合。,3.ROPES机器人规划系统,人工智能自动规划,第19页,8.2任务规划,例：,NAO机器人检球动作。,人工智能自动规划,第20页,