人工智能基础07--自动规划系统.pptx
《人工智能基础07--自动规划系统.pptx》由会员分享,可在线阅读,更多相关《人工智能基础07--自动规划系统.pptx(50页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、目录o第一章第一章绪论o第二章第二章知知识表示表示 o第三章搜索技第三章搜索技术o第四章推理技第四章推理技术o第五章机器学第五章机器学习 o第六章第六章专家系家系统o第七章自第七章自动规划系划系统o第八章第八章自然自然语言理解言理解o第九章第九章智能控制智能控制o第十章第十章人工智能程序人工智能程序设计培训专用o自自动规划概述划概述o基于基于谓词逻辑的的规划划oSTRIPS规划系划系统o分分层规划划o基于基于专家系家系统的机器人的机器人规划划o轨迹迹规划划简介介培训专用7.1 自动规划概述7.1.1规划的概念及作用划的概念及作用1.规划的概念划的概念定定义7.1从某个特定的从某个特定的问题状状
2、态出出发,寻求一系列行求一系列行为动作,作,并建立一个操作序列,直到求得目并建立一个操作序列,直到求得目标状状态为止。止。这个求解个求解过程就程就称称为规划划。定定义7.2规划是划是对某个待求解某个待求解问题给出求解出求解过程的步程的步骤。规划涉及如何将划涉及如何将问题分解分解为若干相若干相应的子的子问题,以及如何,以及如何记录和和处理理问题求解求解过程中程中发现的各子的各子问题间的关系。的关系。定定义7.3规划系划系统是一个涉及有关是一个涉及有关问题求解求解过程步程步骤的系的系统。如如计算机或算机或飞机机设计、火、火车或汽或汽车运运输路径、路径、财政和政和军事事规划等划等问题。培训专用7.1
3、 自动规划概述7.1.1规划的概念及作用划的概念及作用例:例:救援仿真机器人系救援仿真机器人系统(RoboCupRescueSimulationSystem,RCRSS)消防智能体消防智能体医医疗智能体智能体警察智能体警察智能体普通市民普通市民中心智能体中心智能体路障路障避避难所所着火建筑物着火建筑物普通建筑物)普通建筑物)培训专用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.2 基于谓词逻辑的规划用用谓词逻辑
7、来描述世界模型及来描述世界模型及规划划过程。程。o世界模型的世界模型的谓词逻辑表示表示n定定义谓词n确定确定问题初始状初始状态n确定确定问题目目标状状态n确定基本操作确定基本操作o基于基于谓词逻辑规划的基本划的基本过程程n问题分解分解n子子问题规划划n得到操作序列得到操作序列培训专用7.3 STRIPS规划系统7.3.1积木世界的机器人木世界的机器人规划划求解机器人完成求解机器人完成规定工作的定工作的动作序列作序列BACCBA机械手机械手机械手机械手(a)(b)培训专用7.3 STRIPS规划系统7.3.1积木世界的机器人木世界的机器人规划划1.积木世界的机器人木世界的机器人问题机器人能机器人
8、能够执行的行的动作作举例如下:例如下:unstack(a,b):把堆放在:把堆放在积木木b上的上的积木木a拾起。在拾起。在进行行这个个动作之前,作之前,要求机器人的手要求机器人的手为空手,且空手,且积木木a的的顶上是空的。上是空的。stack(a,b):把把积木木a堆放在堆放在积木木b上。上。动作之前要求机械手必作之前要求机械手必须已抓住已抓住积木木a,而且,而且积木木b顶上必上必须是空的。是空的。pickup(a):从桌面上拾起从桌面上拾起积木木a,并抓住它不放。在,并抓住它不放。在动作之前要求作之前要求机械手机械手为空手,而且空手,而且积木木a顶上没有任何上没有任何东西。西。putdown
9、(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.3.1积木世界的机器人木世界的机器人规划划2.用用F规则求
10、解求解规划序列划序列采用采用F规则表示机器人的表示机器人的动作,作,这是一个叫做是一个叫做STRIPS规划系划系统的的规则,它由,它由3部分部分组成:成:第一部分是先决条件。第一部分是先决条件。为了使了使F规则能能够应用到状用到状态描述中去。描述中去。第二部分是一个叫做第二部分是一个叫做删除表的除表的谓词。当一条。当一条规则被被应用于某个状用于某个状态描述或数据描述或数据库时,就从,就从该数据数据库删去去删除表的内容。除表的内容。第三部分叫做添加表。当把某条第三部分叫做添加表。当把某条规则应用于某数据用于某数据库时,就把,就把该添添加表的内容添加表的内容添进该数据数据库。培训专用7.3 STR
11、IPS规划系统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)培训专用7.3 STRIPS规划系统7.3.2STRIPS规划系划系统斯坦福大学人工智能研究所于斯坦福大学人工智能研究所于1966-72年研制的年研制的Shakey机器人是第一机器人是第一台能台能够进行行行行动推理的多用移推理的多用移动机器人
12、,机器人,该项目融合了机器人目融合了机器人视觉、机器人学和自、机器人学和自动推理研究成果。机器人的任推理研究成果。机器人的任务是在一些相是在一些相连的房的房间里,将用里,将用户指定的箱子推到指定的位置。指定的箱子推到指定的位置。对于用于用户输入的入的每一个任每一个任务,Shakey自主地自主地规划完成划完成该任任务的行的行动并依次并依次执行。行。Shakey项目技目技术:规划划语言言STRIPS(STanfordResearchInstituteProblemSolverSTRIPS)和)和A*算法等。算法等。STRIPS语言用来描述外部世界模型并支持任言用来描述外部世界模型并支持任务规划,它
13、提供了框划,它提供了框架架问题的一种的一种简洁、高效的解法,但理、高效的解法,但理论上并不完上并不完备。培训专用7.3 STRIPS规划系统7.3.2STRIPS规划系划系统STRIPS系系统的的组成如下:成如下:(1)世界模型。世界模型。为一一阶谓词演算公式。演算公式。(2)操作符操作符(F规则)。包括先决条件、。包括先决条件、删除表和添加表。除表和添加表。(3)操作方法。操作方法。应用状用状态空空间表示和中表示和中间-结局分析。局分析。规划划过程程每个每个STRIPS问题的解答的解答为某个某个实现目目标的操作符序列,即达到的操作符序列,即达到目目标的的规划。划。A Service Robo
14、t Copes with Changes Understanding,Learning,Planning,and Acting培训专用7.4 分层规划探索探索规划划时首先只考首先只考虑一一层的的细节,然后再注意,然后再注意规划中比划中比这一一层低低一一层的的细节,所以把它叫做,所以把它叫做长度度优先搜索。先搜索。NOAH规划系划系统1.应用最小用最小约束策略束策略一个一个寻找非找非线性性规划而不必考划而不必考虑操作符序列的所有排列的方法是把最操作符序列的所有排列的方法是把最少少约束策略束策略应用来用来选择操作符操作符执行次序的行次序的问题。问题求解系求解系统NOAH采用一种网采用一种网络结构来
15、构来记录它所它所选取的操作符取的操作符之之间所需要的排序。它也分所需要的排序。它也分层进行操作运算,即首先建立起行操作运算,即首先建立起规划的抽象划的抽象轮廓,然后在后廓,然后在后续的各步中,填入越来越多的的各步中,填入越来越多的细节。培训专用7.4 分层规划2.检验准准则准准则法已被法已被应用于各种用于各种规划生成系划生成系统。对于早期的系于早期的系统,如,如HACKER系系统,准,准则只用于舍弃不只用于舍弃不满足的足的规划。在划。在NOAH系系统中,准中,准则被用来提出推定的方法以便修正所被用来提出推定的方法以便修正所产生的生的规划。划。第一个涉及的准第一个涉及的准则是是归结矛盾准矛盾准则
16、。第二个准第二个准则叫做消除多余先决条件准叫做消除多余先决条件准则,包括除去,包括除去对子目子目标的的多余多余说明。明。可以把分可以把分层规划和最少划和最少约束策略十分直接地束策略十分直接地结合起来,以求得非合起来,以求得非线性性规划而不划而不产生一个生一个庞大的搜索大的搜索树。培训专用7.5 基于专家系统的机器人规划1.系系统结构及构及规划机理划机理(1)知)知识库:用于存:用于存储某些特定某些特定领域的域的专家知家知识和和经验,包括机,包括机器人工作器人工作环境的世界模型、状境的世界模型、状态、物体描述等事、物体描述等事实和可行操作或和可行操作或规则等。等。(2)控制策略:包含控制策略:包
17、含综合机理,确定系合机理,确定系统应当当应用什么用什么规则以及采取什么方式去以及采取什么方式去寻找找该规则。(3)推理机:用于推理机:用于记忆所采用的所采用的规则和控制策略及推理策略。和控制策略及推理策略。(4)知)知识获取:首先取:首先获取某特定域的取某特定域的专家知家知识。然后用程序。然后用程序设计语言把言把这些知些知识变换为计算机程序。最后把它算机程序。最后把它们存入知存入知识库待用。待用。培训专用7.5 基于专家系统的机器人规划(5)解解释与与说明:通明:通过用用户接口,在接口,在专家系家系统与用与用户之之间进行行对话,从而使用,从而使用户能能够输入数据、提出入数据、提出问题、知道推理
18、、知道推理结果以及了解果以及了解推理推理过程等。程等。2.任任务级机器人机器人规划三要素划三要素(1)建立模型:世界模型。)建立模型:世界模型。(2)任)任务说明:定明:定义状状态及状及状态变换次序。次序。(3)程序)程序综合。合。3.ROPES机器人机器人规划系划系统培训专用7.6 轨迹规划简介 轨迹:机械手在运迹:机械手在运动过程中的位移、速度和加速度。程中的位移、速度和加速度。轨迹迹规划:根据任划:根据任务的要求,的要求,计算出算出预期的期的轨迹。迹。在机械手运在机械手运动学和学和动力学基力学基础上,上,讨论在关在关节空空间和笛卡和笛卡尔空空间中机器人运中机器人运动的的轨迹迹规划和划和轨
19、迹生成方法迹生成方法培训专用7.6 轨迹规划简介 例:例:NAO机器人机器人检球球动作。作。培训专用地球上的生物物种在漫长的过程中形成了丰富的行为特性,并地球上的生物物种在漫长的过程中形成了丰富的行为特性,并地球上的生物物种在漫长的过程中形成了丰富的行为特性,并地球上的生物物种在漫长的过程中形成了丰富的行为特性,并且一直不断地完善和发展,以更好地适应其所生存的环境。生物群且一直不断地完善和发展,以更好地适应其所生存的环境。生物群且一直不断地完善和发展,以更好地适应其所生存的环境。生物群且一直不断地完善和发展,以更好地适应其所生存的环境。生物群体和自然生态系统可以通过自身的演化就能使许多在人类看
20、起来高体和自然生态系统可以通过自身的演化就能使许多在人类看起来高体和自然生态系统可以通过自身的演化就能使许多在人类看起来高体和自然生态系统可以通过自身的演化就能使许多在人类看起来高度复杂的优化问题得到完美解决。因此,各种模仿生物群体的智能度复杂的优化问题得到完美解决。因此,各种模仿生物群体的智能度复杂的优化问题得到完美解决。因此,各种模仿生物群体的智能度复杂的优化问题得到完美解决。因此,各种模仿生物群体的智能仿生算法被相继提出,得到了深入研究和应用实践。仿生算法被相继提出,得到了深入研究和应用实践。仿生算法被相继提出,得到了深入研究和应用实践。仿生算法被相继提出,得到了深入研究和应用实践。群智
21、能思想的产生主要源于复杂适应系统理论以及人工生命的群智能思想的产生主要源于复杂适应系统理论以及人工生命的群智能思想的产生主要源于复杂适应系统理论以及人工生命的群智能思想的产生主要源于复杂适应系统理论以及人工生命的研究。研究。研究。研究。群智能算法群智能算法群智能思想起源群智能思想起源培训专用群智能算法群智能算法群智能思想起源群智能思想起源复杂适应系统复杂适应系统(ComplexAdaptiveSystem,CAS)理论理论:1994年由年由Holland教授正教授正式提出。式提出。CAS中成员称为具有适应性的主体中成员称为具有适应性的主体,简称主体。简称主体。主体的适应性主体的适应性,是指它能
22、够与环境以及其它主体进行交流,在交流的过程中是指它能够与环境以及其它主体进行交流,在交流的过程中“学习学习”或或“积累经验积累经验”,并且根据学到的经验改变自身的结构和行为方式。,并且根据学到的经验改变自身的结构和行为方式。CAS具有四个基本特点具有四个基本特点:(1)首先)首先,主体是主动的、活的实体。具有适应性的主体的概念把个体主动性提高主体是主动的、活的实体。具有适应性的主体的概念把个体主动性提高到了系统进化基本动因的位置到了系统进化基本动因的位置,从而成为研究与考察宏观行为的出发点。从而成为研究与考察宏观行为的出发点。(2)其次)其次,个体与环境个体与环境(包括个体之间包括个体之间)之
23、间的相互影响、相互作用是系统演变和之间的相互影响、相互作用是系统演变和进化的主要动力。相互作用是进化的主要动力。相互作用是“可记忆可记忆”的的,它表现为进化过程中每个个体的结它表现为进化过程中每个个体的结构和行为方式的变化,以不同的方式构和行为方式的变化,以不同的方式“存储存储”在个体内部。在个体内部。培训专用群智能算法群智能算法群智能思想起源群智能思想起源(3)再次)再次,这种方法不像许多其他的方法那样这种方法不像许多其他的方法那样,把宏观和微观截然分开把宏观和微观截然分开,而是把它们有机地联系起来。而是把它们有机地联系起来。(4)最后)最后,这种建模方法还引进了随机因素的作用这种建模方法还
24、引进了随机因素的作用,使它具有更强使它具有更强的描述和表达能力。随机因素的影响不仅影响状态的描述和表达能力。随机因素的影响不仅影响状态,而且影响组织结而且影响组织结构和行为方式。具有主动性的个体会接受教训构和行为方式。具有主动性的个体会接受教训,总结经验总结经验,并且以某种方式并且以某种方式把把“经历经历”记住记住,使之使之“固化固化”在自己以后的行为方式中。在自己以后的行为方式中。CAS理论提供了模拟生物、理论提供了模拟生物、生态、生态、经济、经济、社会等复杂系统的巨大社会等复杂系统的巨大潜力。潜力。培训专用群智能算法群智能算法群智能思想起源群智能思想起源人工生命人工生命(Artificia
25、lLife,AL)是用来研究具有某些生命基本特征的人工系统。是用来研究具有某些生命基本特征的人工系统。近年来近年来,人工生命的研究发展非常快人工生命的研究发展非常快,在某些方面的研究已与传统的生物科学形成了在某些方面的研究已与传统的生物科学形成了互补。人工生命包括两方面的内容互补。人工生命包括两方面的内容:如何利用计算技术研究生物现象如何利用计算技术研究生物现象;如何利用生物技术研究计算问题。如何利用生物技术研究计算问题。第二部分的内容的研究中,现已经有了很多源于生物现象的计算技巧,例如,第二部分的内容的研究中,现已经有了很多源于生物现象的计算技巧,例如,人工神经网络是简化的大脑模型,遗传算法
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 基础 07 自动 规划系统
限制150内