規(guī)劃提出能達到一定目標的行動序列的任務(wù)

1、規(guī)劃提出能達到一定目標的行動序列的任務(wù)主要內(nèi)容p規(guī)劃問題l規(guī)劃問題語言：語法和語義p狀態(tài)空間搜索規(guī)劃l前向、后向p利用問題的表示的規(guī)劃算法l偏序規(guī)劃l命題邏輯規(guī)劃p規(guī)劃方法分析現(xiàn)實世界問題的困難p假設(shè)一個問題智能使用標準的搜索算法l什么樣的行動是相關(guān)的？n例子：購買“人工智能教材”，假設(shè)對于每一個10位數(shù)字的ISBN號碼都有一個購買行動n遍歷搜索vs.后項搜索l如何尋找一個好的啟發(fā)函數(shù)？n例如在線購買4本不同的書，4個步驟共有1040規(guī)劃n狀態(tài)耗散的估計：所要買書的剩余數(shù)目應(yīng)是一個好的估計。nProblem-dependent vs. independent：啟發(fā)函數(shù)取未滿足的合取式的數(shù)目l如

2、何將問題分解？n假設(shè)大部分現(xiàn)實世界問題是近似可分解的：需要做些附加工作來合并子規(guī)劃Planning languagepWhat is a good language?lExpressive enough to describe a wide variety of problems.lRestrictive enough to allow efficient algorithms to operate on it.lPlanning algorithm should be able to take advantage of the logical structure of the problem

3、.pSTRIPS and ADLGeneral language featurespRepresentation of statesl Decompose the world in logical conditions and represent a state as a conjunction of positive literals (atomic sentences)n Propositional literals: Poor Unknownn FO-literals (grounded and function-free): At(Plane1, Melbourne) At(Plane

4、2, Sydney)l Closed world assumption: conditions not mentioned are assumed falsepRepresentation of goalsl Partially specified state and represented as a conjunction of positive ground literalsl A goal is satisfied if the state contains all literals in goal.General language features (2)pRepresentation

5、s of actionslAction = 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)nAction name and parameter listnPrecondition (conj. of function-free literals)nEffect (conj of funct

6、ion-free literals and P is True and P is false)lAdd-list vs delete-list in EffectLanguage semanticspHow do actions affect states?lAn action is applicable in any state that satisfies the precondition.lFor FO action schema applicability involves a substitution for the variables in the PRECOND.lEx: At(

7、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)pThe result of executing action a in state s is the state s ls is same as s exceptnAny positive liter

8、al P in the effect of a is added to snAny negative literal P is removed from sExample in previous page:At(P1,SFO) At(P2,SFO) Plane(P1) Plane(P2) Airport(JFK) Airport(SFO)lSTRIPS assumption: avoids representational frame problemnevery literal NOT in the effect remains unchangedpSolution is a sequence

9、 such that inigoalExpressiveness and extensionsp STRIPS is simplified l Important limit: function-free literalsl Allows for propositional representationpFunction symbols lead to infinitely many states and actionspRecent extension:Action Description language (ADL)Action(Fly(p:Plane, from: Airport, to

10、: Airport),PRECOND: At(p,from) (from to)EFFECT: At(p,from) At(p,to) p Standardization : Planning domain definition language (PDDL)例子：積木世界p一組放在桌子上的立方體積木，積木能夠被疊放，但是只有一塊積木能夠直接放在另一塊的上面。一個機器臂能夠拿起一塊積木并把它移到別的位置，無論是在桌子上還是在另一塊積木上。機器臂每次只能拿起一塊積木。Examples of planning in Blocks WorldpInit(On(A, Table) On(B,Table

11、) On(C,Table) Block(A) Block(B) Block(C) Clear(A) Clear(B) Clear(C)pGoal(On(A,B) On(B,C)pClear(b) defined as “there is a clear space on b to hold a block”pAction(Move(b,x,y)PRECOND: On(b,x) Clear(b) Clear(y) Block(b) (b x) (b y) (x y) EFFECT: On(b,y) Clear(x) On(b,x) Clear(y)pAction(MoveToTable(b,x)

12、PRECOND: On(b,x) Clear(b) Block(b) (b x) EFFECT: On(b,Table) Clear(x) On(b,x) pNote: we introduce x y to block spurious actions such as Move(B,C,C)注意負文字主要內(nèi)容p規(guī)劃問題l規(guī)劃問題語言：語法和語義p狀態(tài)空間搜索規(guī)劃l前向、后向p利用問題的表示的規(guī)劃算法l偏序規(guī)劃l命題邏輯規(guī)劃p規(guī)劃方法分析狀態(tài)空間搜索規(guī)劃p前向搜索p后向搜索p啟發(fā)式函數(shù)Planning with state-space searchpBoth forward and backw

13、ard search possiblepProgression plannerslforward state-space searchlConsider the effect of all possible actions in a given statepRegression planners lbackward state-space searchlTo achieve a goal, what must have been true in the previous state?Progression and regressionProgression algorithmpFormulat

14、ion as state-space search problem:lInitial state = initial state of the planning problemnLiterals not appearing are falselActions = those whose preconditions are satisfiednAdd positive effects, delete negativelGoal test = does the state satisfy the goal?lStep cost = each action costs 1pNo functions

15、any graph search that is complete is a complete planning algorithm.pInefficient: (1) irrelevant action problem (2) good heuristic required for efficient searchRegression algorithmp How to determine predecessors?l What are the states from which applying a given action leads to the goal?Goal state = A

16、t(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.p Actions must not undo desired literals (consistent)pMain advantage:

17、only relevant actions are considered.l Often much lower branching factor than forward search.Regression algorithm(2)pGeneral process for predecessor constructionl Give a goal description Gl Let A be an action that is relevant and consistentl The predecessors is as follows:n Any positive effects of A

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

19、-space searchpNeither progression or regression are very efficient without a good heuristic.lHow many actions are needed to achieve the goal?lExact solution is NP hard, find a good estimate pTwo approaches to find admissible heuristic:lThe optimal solution to the relaxed problem.nRemove all precondi

20、tions from actionslThe subgoal independence assumption:The cost of solving a conjunction of subgoals is approximated by the sum of the costs of solving the subproblems independently.主要內(nèi)容p規(guī)劃問題l規(guī)劃問題語言：語法和語義p狀態(tài)空間搜索規(guī)劃l前向、后向p利用問題的表示的規(guī)劃算法l偏序規(guī)劃l命題邏輯規(guī)劃p規(guī)劃方法分析Partial-order planningpProgression and regression

21、 planning are totally ordered plan search forms.lThey cannot take advantage of problem decomposition.nDecisions must be made on how to sequence actions on all the subproblemspLeast commitment strategy:lDelay choice during searchlStart from “obvious” and “important” decisionsShoe exampleGoal(RightSho

22、eOn LeftShoeOn)Init()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, righ

23、tshoe independently and combine them togetherpartial order planningPartial-order planningpAny planning algorithm that can place two actions into a plan without which comes first is a POL.POL as a search problemp States are (mostly unfinished) plans.l The empty plan contains only start and finish act

24、ions.pEach plan has 4 components:l A set of actions (steps of the plan)l A set of ordering constraints: A Bn Cycles represent contradictions.l A set of causal linksn The 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 com

25、e after A and before B)l A set of open preconditions.n If precondition is not achieved by action in the plan. Ap BPOL as a search problem (2)pA plan is consistent iff there are no cycles in the ordering constraints and no conflicts with the causal links.pA consistent plan with no open preconditions

26、is a solution.pA partial order plan is executed by repeatedly choosing any of the possible next actions.lThis flexibility is a benefit in non-cooperative environmentslAlso make it easy for merging small plannings into a large planningSolving POLpAssume propositional planning problems:lThe initial pl

27、an contains Start and Finish, the ordering constraint Start B and the ordering constraing A B is added to the plan.nIf A is new also add start A and A B to the planlResolve conflicts between new causal link and all existing actionslResolve conflicts between action A (if new) and all existing causal

28、links.Process summarypOperators on partial planslAdd link from existing plan to open precondition.lAdd a step to fulfill an open condition.lOrder one step w.r.t another to remove possible conflictspGradually move from incomplete/vague plans to complete/correct planspBacktrack if an open condition is

29、 unachievable or if a conflict is unresolvable.Example: Spare 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,Groun

30、d) Action(PutOn(Spare,Axle)PRECOND: At(Spare,Groundp) At(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 problempIntial plan: Start with EFFECTS and Finish with PRECOND.So

31、lving the problemp Intial plan: Start with EFFECTS and Finish with PRECOND.p Pick an open precondition: At(Spare, Axle)p Only PutOn(Spare, Axle) is applicablep Add causal link: p Add constraint : PutOn(Spare, Axle) FinishFinishAxleSparePutOnAxleSpareAt),(),(Solving the problemp Pick an open precondi

32、tion: At(Spare, Ground)p Only Remove(Spare, Trunk) is applicablep Add causal link: p Add constraint : Remove(Spare, Trunk) PutOn(Spare,Axle)Remove(Spare,Trunk)At(Spare,Ground )PutOn(Spare,Axle)Remove(Spare,Trunk)At(Spare,Ground )PutOn(Spare,Axle)Solving the problempPick an open precondition: At(Spar

33、e, Axle)pLeaveOverNight is applicablepconflict: pTo resolve, add constraint : LeaveOverNight Remove(Spare, Trunk)pAdd causal link:LeaveOverNightAt(Spare,Ground) PutOn(Spare,Axle)Solving the problempPick an open precondition: At(Spare, Trunk)pOnly Start is applicablepAdd causal link: pConflict: of ca

34、usal link with effect At(Spare,Trunk) in LeaveOverNightlNo re-ordering solution possible.pbacktrackStartAt(Spare,Trunk) Remove(Spare,Trunk)Solving the problempRemove LeaveOverNight and its causal linkspAgain choose an applicable action for At(Spare, Axle): RemoveFlatAxle is chosen pAdd casual linkpA

35、dd constraint StartRemoveFlatAxlepCheck consistency and OkpChoose Start to obtain the precondition of RemoveFlatAxlepFinish),(),(Re),(AxleSparePutOnAxleFlatmoveGroundSpareAtSome details pWhat happens when a first-order representation that includes variables is used?lComplicates the process of detect

36、ing and resolving conflicts.lCan be resolved by introducing inequality constrainst.pCSPs most-constrained-variable constraint can be used for planning algorithms to select a PRECOND.HWp11.4Planning with propositional logicp Planning can be done by proving theorem in situation calculus.p Here: test t

37、he satisfiability of a logical sentence:p Sentence contains propositions for every action occurrence.l A model will assign true to the actions that are part of the correct plan and false to the othersl An assignment that corresponds to an incorrect plan will not be a model because of inconsistency w

38、ith the assertion that the goal is true.l If the planning is unsolvable the sentence will be unsatisfiable.initial state all possible action descriptions goalSATPLAN algorithmfunction SATPLAN(problem, Tmax) return solution or failureinputs: problem, a planning problem Tmax, an upper limit to the pla

39、n 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-SOLUTION(assignment, mapping)return failurecnf, mapping TRANSLATE-TO_SAT(problem, T)p Distinct propositions for assertions about each time step.l Superscripts

40、 denote the time stepAt(P1,SFO)0 At(P2,JFK)0l No CWA thus specify which propositions are not trueAt(P1,JFK)0 At(P2,SFO)0l Unknown propositions are left unspecified.pThe goal is associated with a particular time-stepl But which one?cnf, mapping TRANSLATE-TO_SAT(problem, T)p How to determine the time

41、step where the goal will be reached?l Start at T=0n Assert At(P1,SFO)0 At(P2,JFK)0l Failure . Try T=1n Assert At(P1,SFO)1 At(P2,JFK)1ll Repeat this until some minimal path length is reached. l Termination is ensured by Tmaxcnf, mapping TRANSLATE-TO_SAT(problem, T)p How to encode actions into PL?l 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)l Such an axiom is required