人工智能原理人工智能原理 (45).pdf
《人工智能原理人工智能原理 (45).pdf》由会员分享,可在线阅读,更多相关《人工智能原理人工智能原理 (45).pdf(22页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、Artificial IntelligenceClassic PlanningArtificial Intelligence2Contents 8.2.1.Planning as State-Space Search 8.2.2.Planning Graphs 8.2.3.Other Classical Planning ApproachesArtificial Intelligence:Planning:Classic and Real-world Planning3 1)Forward state-space search 前向状态空间搜索 starting in the initial
2、state,从初始状态开始,using the problems actions,运用该问题的动作,search forward for a member of the goal states.朝着一个目标状态向前搜索。Two approaches to searching for a plan 搜索计划的两种方式8.2.1.Planning as State-Space SearchArtificial Intelligence:Planning:Classic and Real-world Planning4 2)Backward relevant-states search 后向状态空间
3、搜索 starting at the set of states representing the goal,从表示该目标的状态集开始,using the inverse of the actions,运用反向的动作,search backward for the initial state.朝着初始状态向后搜索。Two approaches to searching for a plan 搜索计划的两种方式8.2.1.Planning as State-Space SearchArtificial Intelligence:Planning:Classic and Real-world Pl
4、anning5 Think of a search problem as a graph 将搜索问题视为一个图 where the nodes are states and the edges are actions,to find a path connecting the initial state to a goal state.其中节点表示状态、边为动作,寻找一条连接初始状态至某个目标状态的路径。Two ways to make this problem easier 该问题简化的两种方式 adding edges 增加边add more edges to the graph,maki
5、ng it easier to find a path.在图上增加更多的边,使之容易找到一条路径。state abstraction 状态抽象group multiple nodes together,form an abstraction of the state space that has fewer states,thus is easier to search.将多个节点组织在一起,形成具有较少状态的一个状态空间抽象,从而容易搜索。Heuristics for planning 规划的启发法8.2.1.Planning as State-Space SearchArtificial
6、Intelligence:Planning:Classic and Real-world Planning6 1)Ignore-preconditions heuristic 忽略前提启发法 Drop all preconditions from actions.放弃动作中所有的前提条件。Every action becomes applicable in every state,and any single goal fluent can be achieved in one step.每个动作变成可作用于每个状态,并且任一目标变数可以用一个步骤实现。Two heuristics by ad
7、ding edges to the graph 图中添加边的两种启发法8.2.1.Planning as State-Space SearchExample:8-puzzle as a planning problem8数码难题作为规划问题Removing the two preconditions,any tile can move in one action to any space,and get the number-of-misplaced-tiles heuristic.去掉两个前提条件后,任何棋子可以用一个动作移动到任意空间,从而得到错放棋子个数的启发法。Action(Slide
8、(t,s1,s2),PRECOND:On(t,s1)Tile(t)Blank(s2)Adjacent(s1,s2)EFFECT:On(t,s2)Blank(s1)On(t,s1)Blank(s2)Artificial Intelligence:Planning:Classic and Real-world Planning7 2)Ignore-delete-lists heuristic 忽略删除表启发法 Remove the delete lists from all actions,从所有动作中移除删除表,i.e.,removing all negative literals from e
9、ffects.即,从作用中删除所有的否定文字。That makes it possible to make monotonic progress towards goal:这样就使其可以朝向目标单调进展:no action will ever undo progress made by another action.任何动作都不会取消另一个动作的进展。Two heuristics by adding edges to the graph 图中添加边的两种启发法8.2.1.Planning as State-Space SearchArtificial Intelligence:Planning
10、:Classic and Real-world Planning8 A directed graph organized into levels:组成层次的有向图:first,a level S0for initial state,consisting of nodes representing each fluent;首先,初始状态的层次 S0,包含 表示每个变数的节点;then,a level A0consisting of nodes for each action may be applicable in S0;然后,层次 A0,包含可能适用于 S0的每个动作的节点;then,alte
11、rnating levels Sifollowed by Ai;然后,交替进入层次 Si,接着是 Ai;until we reach a termination condition.直到到达一个结束条件。Work only for propositional planning problems 仅适用于命题规划问题 ones with no variables.无变量项。What is a planning graph 什么是规划图8.2.2.Planning GraphsArtificial Intelligence:Planning:Classic and Real-world Plann
12、ing9Example 1:Have cake and eat cake too 有蛋糕和吃蛋糕8.2.2.Planning GraphsThe“have cake and eat cake too”problem.“有蛋糕和吃蛋糕”问题The“have cake and eat cake too”planning graph.“有蛋糕和吃蛋糕”规划图Init(Have(Cake)Goal(Have(Cake)Eaten(Cake)Action(Eat(Cake)PRECOND:Have(Cake)EFFECT:Have(Cake)Eaten(Cake)Action(Bake(Cake)PRE
13、COND:Have(Cake)EFFECT:Have(Cake)Artificial Intelligence:Planning:Classic and Real-world Planning10GRAPH-PLANalgorithm GRAPH-PLAN算法8.2.2.Planning GraphsIt calls EXPAND-GRAPHto add a level,until either a solution is found by EXTRACT-SOLUTION,or no solution is possible.调用EXPAND-GRAPH来增加一层,直到通过调用EXTRACT
14、-SOLUTION找到一个解,或者没有可能存在的解。function GRAPH-PLAN(problem)returns solution or failuregraph INITIAL-PLAN-GRAPH(problem)goals CONJUNCTS(problem.GOAL)nogoods an empty hash tablefor tl=0 to doif goals all non-mutex in Stof graph thensolution EXTRACT-SOLUTION(graph,goals,NUMLEVELS(graph),nogoods)if solution
15、failure then return solutionif graph and nogoods have both leveled off then return failuregraph EXPAND-GRAPH(graph,problem)Artificial Intelligence:Planning:Classic and Real-world Planning11Example 2:Spare tire problem 备用轮胎问题8.2.2.Planning GraphsThe initial state has a flat tire on the axle and a goo
16、d spare tire in the trunk,and the goal isto have the spare tire properly mounted onto the cars axle.初始状态是车轴上有一个瘪的轮胎并且后备箱里有一个好的备胎,而目标是将这个备胎正确地装在车轴上。Init(Tire(Flat)Tire(Spare)At(Flat,Axle)At(Spare,Trunk)Goal(At(Spare,Axle)Action(Remove(obj,loc),PRECOND:At(obj,loc)EFFECT:At(obj,loc)At(obj,Ground)Action
17、(PutOn(t,Axle),PRECOND:Tire(t)At(t,Ground)At(Flat,Axle)EFFECT:At(t,Ground)At(t,Axle)Action(LeaveOvernight,PRECOND:EFFECT:At(Spare,Ground)At(Spare,Axle)At(Spare,Trunk)At(Flat,Ground)At(Flat,Axle)At(Flat,Trunk)Artificial Intelligence:Planning:Classic and Real-world Planning12Example 2:Planning graph f
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能原理人工智能原理 45 人工智能 原理 45
限制150内