文档介绍：自动规划概述
任务规划
路经规划
轨迹规划简介
小结
Automatic Planning 第八章自动规划
自动规划概述 Introduction
Another important application areas of AI
√ Expert system
√ Machine learning
Nature language processing
Automatic planning
Definition of planning
Planning-ones decide a route or process before action to a thing
2
规划的概念和作用
1. 规划的概念
从某个特定的问题状态出发,寻求一系列行为动作,并建立一个操作序列,直到求得目标状态为止。这个求解过程就称为规划。
规划是关于动作的推理。它是一种抽象的和清晰的深思熟虑过程,该过程通过预期动作的期望效果,选择和组织一组动作,其目的是尽可能好地实现一个预先给定的目标。
人工智能辞典对规划和规划系统给出如下定义:
规划是对某个待求解问题给出求解过程的步骤。规划涉及如何将问题分解为若干个相应的子问题,以及如何记录和处理问题求解过程中发现的子问题间的关系。
规划系统是一个涉及有关问题求解过程的步骤的系统。例如,计算机或飞机设计、火车或汽车运输路径、财政和军事等规划问题。
3
2. 规划的作用
在科学发展观的指导下,对于国民经济和社会的重大问题,对于科学技术、工程和民生的重要问题,都需要进行科学规划和决策。决策的优劣将决定行动的成败。智能决策系统和自动规划系统是科学决策的重要手段,它们同专家系统一起将成为21世纪智能管理与决策的得力工具。
例如:国家和地区国民经济和社会发展计划、财政预算、三峡工程、南水北调工程、大飞机制造项目、财政与金融调控等。
4
规划的分类和问题分解途经
1. 规划的分类
按规划内容分
按规划方法分
按规划实质分
任务规划对求解问题的目标和任务等进行规划,又可称为高层规划。
路径规划对求解问题的途径、路径、代价等进行规划,又可称为中层规划。
轨迹规划对求解问题的空间几何轨迹及其生成进行规划,又可称为底层规划。
2. 问题分解途径
3. 域的预测和规划的修正
5
执行规划系统任务的一般方法
机器人规划系统必须具有执行下列各项任务的方法:
根据最有效的启发信息,选择要用的最好规则。
应用所选规则计算因应用该规则而生成的新状态。
检验求得的解答。
检验空端(dead end),以便舍弃它们,使系统的求解工作向着更有效的方向进行。
检验殆正确(almost correct solution)的解答,并应用具体的技术使之完全正确。
选择和应用规则
检验解答与空端
修正殆正确解
6
任务规划 Task Planning 积木世界的机器人规划
积木世界由一些有标记的立方形积木互相堆迭在一起构成;机器人有个可移动的机械手,它可以抓起积木块并把积木从一处移动至另一处。见右例。
A
C
B
机械手
7
在这类例子中机器人能够执行的动作举例如下:
unstack(a,b):把堆放在积木B上的积木A捡起。
在进行这个动作之前,要求机器人的
手为空手,而且积木A的顶上也是空的。
stack(a,b):把积木A堆放在积木B上。
动作之前要求机械手必须已抓住积木
A,而且积木B顶上必须是空的。
pickup(a):从桌面上拾起积木A,并抓住它不放。
在动作之前要求机械手为空手,而且积木A顶上没有任何东西。
putdown(a):把积木A放置到桌面上。要求动作之前机械手已抓住积木A。
A
C
B
机械手
8
规划工作内容就是综合机器人的动作序列,即在某个给定初始情况下,经过某个动作序列而达到指定的目标。
机器人问题的状态描述和目标描述均可用谓词逻辑公式构成:
ON(a,b):积木A在积木B之上。
ONTABLE(a):积木A在桌面上。
CLEAR(a):积木A顶上没有任何东西。
HOLDING(a):机械手正抓住积木A。
HANDEMPTY:机械手为空手。
A
C
B
机械手
9
积木世界机器人规划问题示例
机器人初始布局问题,(a)所示。
目标问题:(b)所示的积木堆。其中,积木B堆在积木C上面,积木A又堆在积木B上面。
积木世界的机器人问题
C
B
A
机械手
A
B