规划提出能达到一定目标的行动序列的任务ppt课件

1、规划规划：提出能到达一定目的的行动序列的义务基于搜索的问题智能体逻辑规划智能体规划环境经典的：完全可察看、确定性的、有限的、静态的以及离散的。非经典：部分可察看或随机致谢：本讲义部分内容来自Tom Lenaertiridia.ulb.ac.be/tlenaert/teach/slides/AIMA/主要内容规划问题规划问题言语：语法和语义形状空间搜索规划前向、后向利用问题的表示的规划算法偏序规划命题逻辑规划规划方法分析现实世界问题的困难假设一个问题智能运用规范的搜索算法什么样的行动是相关的？例子：购买“人工智能教材，假设对于每一个10位数字的ISBN号码都有一个购买行动遍历搜索vs.后项搜索如

2、何寻觅一个好的启发函数？例如在线购买4本不同的书，4个步骤共有1040规划形状耗散的估计：所要买书的剩余数目应是一个好的估计。Problem-dependent vs. independent：启发函数取未满足的合取式的数目如何将问题分解？假设大部分现实世界问题是近似可分解的：需求做些附加任务来合并子规划Planning languageWhat is a good language?Expressive enough to describe a wide variety of problems.Restrictive enough to allow efficient algorithms

3、to operate on it.Planning algorithm should be able to take advantage of the logical structure of the problem.STRIPS and ADLGeneral language featuresRepresentation of statesDecompose the world in logical conditions and represent a state as a conjunction of positive literals (atomic sentences)Proposit

4、ional literals: Poor UnknownFO-literals (grounded and function-free): At(Plane1, Melbourne) At(Plane2, Sydney)Closed world assumption: conditions not mentioned are assumed falseRepresentation of goalsPartially specified state and represented as a conjunction of positive ground literalsA goal is sati

5、sfied if the state contains all literals in goal.General language features (2)Representations of actionsAction = PRECOND + EFFECTAction(Fly(p,from, to),PRECOND: At(p,from) Plane(p) Airport(from) Airport(to)EFFECT: AT(p,from) At(p,to)= action schema (方式) (p, from, to need to be instantiated)Action na

6、me and parameter listPrecondition (conj. of function-free literals)Effect (conj of function-free literals and P is True and P is false)Add-list vs delete-list in EffectLanguage semanticsHow do actions affect states?An action is applicable in any state that satisfies the precondition.For FO action sc

7、hema applicability involves a substitution for the variables in the PRECOND.Ex: At(P1,JFK) At(P2,SFO) Plane(P1) Plane(P2) Airport(JFK) Airport(SFO)Satisfies : At(p,from) Plane(p) Airport(from) Airport(to)With =p/P1,from/JFK,to/SFOThus the action is applicable.Language semantics (2)The result of exec

8、uting action a in state s is the state s s is same as s exceptAny positive literal P in the effect of a is added to sAny negative literal P is removed from sExample in previous page:At(P1,SFO) At(P2,SFO) Plane(P1) Plane(P2) Airport(JFK) Airport(SFO)STRIPS assumption: avoids representational frame pr

9、oblemevery literal NOT in the effect remains unchangedSolution is a sequence such that inigoalExpressiveness and extensionsSTRIPS is simplified Important limit: function-free literalsAllows for propositional representationFunction symbols lead to infinitely many states and actionsRecent extension:Ac

10、tion Description language (ADL)Action(Fly(p:Plane, from: Airport, to: Airport),PRECOND: At(p,from) (from to)EFFECT: At(p,from) At(p,to) Standardization : Planning domain definition language (PDDL)例子：积木世界一组放在桌子上的立方体积木，积木可以被叠放，但是只需一块积木可以直接放在另一块的上面。一个机器臂可以拿起一块积木并把它移到别的位置，无论是在桌子上还是在另一块积木上。机器臂每次只能拿起一块积木。

11、Examples of planning in Blocks WorldInit(On(A, Table) On(B,Table) On(C,Table) Block(A) Block(B) Block(C) Clear(A) Clear(B) Clear(C)Goal(On(A,B) On(B,C)Clear(b) defined as “there is a clear space on b to hold a blockAction(Move(b,x,y)PRECOND: On(b,x) Clear(b) Clear(y) Block(b) (b x) (b y) (x y) EFFEC

12、T: On(b,y) Clear(x) On(b,x) Clear(y)Action(MoveToTable(b,x)PRECOND: On(b,x) Clear(b) Block(b) (b x) EFFECT: On(b,Table) Clear(x) On(b,x) Note: we introduce x y to block spurious actions such as Move(B,C,C)留意负文字主要内容规划问题规划问题言语：语法和语义形状空间搜索规划前向、后向利用问题的表示的规划算法偏序规划命题逻辑规划规划方法分析形状空间搜索规划前向搜索后向搜索启发式函数Planning

13、 with state-space searchBoth forward and backward search possibleProgression plannersforward state-space searchConsider the effect of all possible actions in a given stateRegression planners backward state-space searchTo achieve a goal, what must have been true in the previous state?Progression and

14、regressionProgression algorithmFormulation as state-space search problem:Initial state = initial state of the planning problemLiterals not appearing are falseActions = those whose preconditions are satisfiedAdd positive effects, delete negativeGoal test = does the state satisfy the goal?Step cost =

15、each action costs 1No functions any graph search that is complete is a complete planning algorithm.Inefficient: (1) irrelevant action problem (2) good heuristic required for efficient searchRegression algorithmHow to determine predecessors?What are the states from which applying a given action leads

16、 to the goal?Goal state = At(C1, B) At(C2, B) At(C20, B)Relevant action for first conjunct: Unload(C1,p,B)Works only if pre-conditions are satisfied.Previous state= In(C1, p) At(p, B) At(C2, B) At(C20, B)Subgoal At(C1,B) should not be present in this state.Actions must not undo desired literals (con

17、sistent)Main advantage: only relevant actions are considered.Often much lower branching factor than forward search.Regression algorithm(2)General process for predecessor constructionGive a goal description GLet A be an action that is relevant and consistentThe predecessors is as follows:Any positive

18、 effects of A that appear in G are deleted.Each precondition literal of A is added , unless it already appears.Any standard search algorithm can be added to perform the search.Termination when predecessor satisfied by initial state.In FO case, satisfaction might require a substitution.Heuristics for

19、 state-space searchNeither progression or regression are very efficient without a good heuristic.How many actions are needed to achieve the goal?Exact solution is NP hard, find a good estimate Two approaches to find admissible heuristic:The optimal solution to the relaxed problem.Remove all precondi

20、tions from actionsThe subgoal independence assumption:The cost of solving a conjunction of subgoals is approximated by the sum of the costs of solving the subproblems independently.主要内容规划问题规划问题言语：语法和语义形状空间搜索规划前向、后向利用问题的表示的规划算法偏序规划命题逻辑规划规划方法分析Partial-order planningProgression and regression planning

21、are totally ordered plan search forms.They cannot take advantage of problem decomposition.Decisions must be made on how to sequence actions on all the subproblemsLeast commitment strategy:Delay choice during searchStart from “obvious and “important decisionsShoe exampleGoal(RightShoeOn LeftShoeOn)In

22、it()Action(RightShoe,PRECOND: RightSockOnEFFECT: RightShoeOn)Action(RightSock,PRECOND: EFFECT: RightSockOn)Action(LeftShoe,PRECOND: LeftSockOnEFFECT: LeftShoeOn)Action(LeftSock,PRECOND: EFFECT: LeftSockOn)Planner: process two action sequences (1)leftsock, leftshoe (2)rightsock, rightshoe independent

23、ly and combine them togetherpartial order planningPartial-order planningAny planning algorithm that can place two actions into a plan without which comes first is a POL.POL as a search problemStates are (mostly unfinished) plans.The empty plan contains only start and finish actions.Each plan has 4 c

24、omponents:A set of actions (steps of the plan)A set of ordering constraints: A BCycles represent contradictions.A set of causal linksThe plan may not be extended by adding a new action C that conflicts with the causal link. (if the effect of C is p and if C could come after A and before B)A set of o

25、pen preconditions.If precondition is not achieved by action in the plan. POL as a search problem (2)A plan is consistent iff there are no cycles in the ordering constraints and no conflicts with the causal links.A consistent plan with no open preconditions is a solution.A partial order plan is execu

26、ted by repeatedly choosing any of the possible next actions.This flexibility is a benefit in non-cooperative environmentsAlso make it easy for merging small plannings into a large planningSolving POLAssume propositional planning problems:The initial plan contains Start and Finish, the ordering const

27、raint Start B and the ordering constraing A B is added to the plan.If A is new also add start A and A B to the planResolve conflicts between new causal link and all existing actionsResolve conflicts between action A (if new) and all existing causal links.Process summaryOperators on partial plansAdd

28、link from existing plan to open precondition.Add a step to fulfill an open condition.Order one step w.r.t another to remove possible conflictsGradually move from incomplete/vague plans to complete/correct plansBacktrack if an open condition is unachievable or if a conflict is unresolvable.Example: S

29、pare tire problemInit(At(Flat, Axle) At(Spare,trunk)Goal(At(Spare,Axle)Action(Remove(Spare,Trunk)PRECOND: At(Spare,Trunk)EFFECT: At(Spare,Trunk) At(Spare,Ground) Action(Remove(Flat,Axle)PRECOND: At(Flat,Axle)EFFECT: At(Flat,Axle) At(Flat,Ground) Action(PutOn(Spare,Axle)PRECOND: At(Spare,Groundp) At(

30、Flat,Axle)EFFECT: At(Spare,Axle) Ar(Spare,Ground)Action(LeaveOvernightPRECOND:EFFECT: At(Spare,Ground) At(Spare,Axle) At(Spare,trunk) At(Flat,Ground) At(Flat,Axle) )Solving the problemIntial plan: Start with EFFECTS and Finish with PRECOND.Solving the problemIntial plan: Start with EFFECTS and Finis

31、h with PRECOND.Pick an open precondition: At(Spare, Axle)Only PutOn(Spare, Axle) is applicableAdd causal link: Add constraint : PutOn(Spare, Axle) FinishSolving the problemPick an open precondition: At(Spare, Ground)Only Remove(Spare, Trunk) is applicableAdd causal link: Add constraint : Remove(Spar

32、e, Trunk) PutOn(Spare,Axle)Solving the problemPick an open precondition: At(Spare, Axle)LeaveOverNight is applicableconflict: To resolve, add constraint : LeaveOverNight Remove(Spare, Trunk)Add causal link:Solving the problemPick an open precondition: At(Spare, Trunk)Only Start is applicableAdd caus

33、al link: Conflict: of causal link with effect At(Spare,Trunk) in LeaveOverNightNo re-ordering solution possible.backtrackSolving the problemRemove LeaveOverNight and its causal linksAgain choose an applicable action for At(Spare, Axle): RemoveFlatAxle is chosen Add casual linkAdd constraint StartRem

34、oveFlatAxleCheck consistency and OkChoose Start to obtain the precondition of RemoveFlatAxleFinishSome details What happens when a first-order representation that includes variables is used?Complicates the process of detecting and resolving conflicts.Can be resolved by introducing inequality constra

35、inst.CSPs most-constrained-variable constraint can be used for planning algorithms to select a PRECOND.HW11.4Planning with propositional logicPlanning can be done by proving theorem in situation calculus.Here: test the satisfiability of a logical sentence:Sentence contains propositions for every act

36、ion occurrence.A model will assign true to the actions that are part of the correct plan and false to the othersAn assignment that corresponds to an incorrect plan will not be a model because of inconsistency with the assertion that the goal is true.If the planning is unsolvable the sentence will be

37、 unsatisfiable.SATPLAN algorithmfunction SATPLAN(problem, Tmax) return solution or failureinputs: problem, a planning problem Tmax, an upper limit to the plan lengthfor T= 0 to Tmax do cnf, mapping TRANSLATE-TO_SAT(problem, T) assignment SAT-SOLVER(cnf)if assignment is not null then return EXTRACT-S

38、OLUTION(assignment, mapping)return failurecnf, mapping TRANSLATE-TO_SAT(problem, T)Distinct propositions for assertions about each time step.Superscripts denote the time stepAt(P1,SFO)0 At(P2,JFK)0No CWA thus specify which propositions are not trueAt(P1,JFK)0 At(P2,SFO)0Unknown propositions are left

39、 unspecified.The goal is associated with a particular time-stepBut which one?cnf, mapping TRANSLATE-TO_SAT(problem, T)How to determine the time step where the goal will be reached?Start at T=0Assert At(P1,SFO)0 At(P2,JFK)0Failure . Try T=1Assert At(P1,SFO)1 At(P2,JFK)1Repeat this until some minimal path length is reached. Termination is ensured by Tmaxcnf, mapping TRANSLATE-TO_SAT(problem, T)How to encode actions into PL?Propositional versions of successor-state axiomsAt(P1,JFK)1 (At(P1,JFK)0 (Fly(P1,JFK,SFO)0 At(P1,JFK)0) (Fly(P1,SFO,JFK)0 At(P1,SFO)0)Such an axiom i