(Dis)advantages of POP ---------------------- - Expressiveness is easily added to algorithm - E.g. Durative actions, see also Weld's least commitment planning article - Same extensions are possible for Prog/Reg, but can significantly increase the branching factor - Search in Classical Planning may be unneccesarily complicated for POP - The search tree is of size B^D (B = branch factor, D = solution depth) - For POP -- D = # of open conditions + # of unsafe links - Yet for Prog/Reg -- D = # of actions - Say, there is a plan with one action with 10,000 preconditions - For POP D = 10,000 (open conditions) - For Prog/Reg D = 1 (action) - B is usually lower for POP because there is no branching on positions of actions - Positition constrained = Each action is bound to a certain time (Prog/Reg) - Precedence constrained = Each action is bound to a certain ordering in relation to the other actions in the plan (POP) - Say we're doing planning with durative actions - a Position constrained plan has to branch on each of the possible starting times for an action (The meeting could start at 10:30, 10:31, 10:32, etc.) - i.e. the dispatching of actions is determined at the time of action selection - A precedence constrained plan would simply say that the meeting should be at a time that doesn't conflict with any of the other actions that the planning agent needs to perform - i.e. the dispatching of actions is determined after the relative sequence of actions is determined. - Durative actions can also increase the depth (D) of problem - Say, there is an action who has several effects that occur throughout the actions duration. To effectively deal with the these effects the action must be broken into smaller unit actions. Thus, increasing D. - Levels of Commitment - Overcommiting for no reason will induce a greater amount of backtracking - E.G. scheduling a meeting a "Tuesday at 10:31:30am" is more commited than scheduling a meeting for "Tuesday morning". Say, someone cannot make the meeting at 10:31:30am, but 10:35:30am, then we'll need to backtrack. However, this wouldn't be the case if we settled on "Tuesday morning" instead because the action of having the meeting is not threatened this way. - Undercommiting causes room for inconsistencies, which can be hard to check - E.G. Say, we've commited to five meetings on Tuesday morning, none of which have a specified time. It is difficult for the planning agent to know if they will actually be able to attend any of these meetings because they haven't committed enough. - Commitment isn't black and white - rather its shades of grey - Another least commitment strategy beyond POP is to allow for disjunctive constraints - Say, there is a goal G1 that needs to be supported, and we have actions a1 ... a100 that all give G1. We could say that one of a1 ... a100 should be used to support G1 but leave it unspecified as to which one is actually performed. This is analagous to software companies outsourcing some of their projects. They know that the project must be completed but don't really care which programmers are the ones that do the job. - Commitment brings about another tastes great, less filling debate beyond branching vs. depth --- the branching factor can also be inversely correlated with the difficulty of consistency checking - **** To some extent we can handle greater branching factors if we have effective heuristics - Of late POP has taken a back seat to finding heuristics for Prog/Reg planners because we can reduce the branching factor without having to do the more complicated search of POP Heuristics for Planning ----------------------- - Planning problems may have many solution plans that are feasible, but some are better than others with respect to many different criterion: - # of actions - Makespan (duration of plan, equal to # of actions when using non-durative actions) - Cost (money, resources, etc.) - Robustness (# of contingencies, probability of success in execution) - We can also have multi-objective criterion, say cost and makespan. - Say, we want to get to L.A. for a meeting. Our options are to take a $50 bus ride that takes 8 hours, or take a $100 plane ride that takes 1 hour. - It isn't clear which is better -- it depends on the user's preferences. A grad student may opt for the bus ride because they need the extra money to eat, but can do a lot of reading on the 8 hour drive. Whereas the professor may opt for the plane ride because they can afford it and need to take care of other business in L.A. before the meeting. - The only time it becomes clear which plan is better is when one plan 'dominates' another. I.e. for all criterion a plan is better. E.G. A third option to get to L.A. is to use your friend's teleporter, which costs nothing for you because they owe you a favor and it will only take 1ms to get to L.A. Clearly, this plan would dominate the others because its faster and cheaper. - The set of non-dominated plans is called the "Pareto Set" - Heuristics are used in the context of A* search, where the goodness of a course of action is determined by the difficulty of reaching the current situation from the start of the search plus the estimated difficulty of reaching a solution (terminating search) from the current situation - Effective heuristics are judged by two criterion: - Admissibility: When estimating the goodness of a particular course of action, if the goodness estimate is always an underestimate, then the heuristic is termed admissible. E.G. BFS is always admissible because it is A* where the h_value is always zero. - Taking the max of several admissible heuristics will always preserve admissibility - Using admissible heuristics guarantees an optimal solution, but not always a quick search for the solution -- thus we also want to consider informedness... - Informedness: An informed heuristic is not necessesarily admissible because informedness is a measure of how close the heuristic estimate of the goodness of a course of action is with respect to the optimal course of action. - In practice, we may sacrifice admissibility for informedness because getting a solution of length n today may be better than getting a solution of n-1 tomorrow. - Heuristics are based on relaxations of the problem - Ideally we want a polynomial time estimate - E.G. - Grid navigation with obstacles - Relaxation is to use straight line distance to estimate distance to objective - Obstacles are not considered because considering them in the heuristic is as difficult as actually doing the planning. - 8-puzzle - # misplaced tiles - relaxes need to consider how many movements needed - Manhattan distance - sum of x and y displacement for each tile - adds more constraints to the estimate -- effectively increases heuristic computation but also increases the informedness of the heuristic ... We have another tastes great less filling debate...... - There is a tradeoff between the informedness of a heuristic and the computation time - Finding the perfect heuristic will drive search to the solution very fast but take a long time to compute, whereas a less perfect heuristic will require more search but would be easier to compute ... this tradeoff tends to be an empirical issue. - Interaction of Subgoals - +ve - Cost of achieving sub-goals together is less than acheiving them independently - One action may achieve several goals at once - E.G. Bundling at McDonald's - The cost of a value meal is cheaper than buying each of the items separately. - Ignoring postive interations hurts admissibilty - -ve - Cost of achieving sub-goals together is more than acheivng them independently - One action may undo the sub-goals acheived by another action - E.G. Having your cake and eating too - Eating the cake will undo having the cake, so to have your cake and eat it too, you must buy two cakes instead of one to achieve the goal. If considering the sub-goals independently, you may think that you only need to buy one cake. - Ignoring negative interactions hurts informedness - independent - The cost of achieving the sub-goals is the same whether they are achieved together or separately. - Types of heuristics for Prog/Reg - Set Difference - The estimate for reaching a terminal state from the current state is the cardinality of the set resulting from the difference of the sets of literals in the current state and the terminal state. - This assumes that each sub-goal is independently achievable and the cost of acheiving each literal is 1. - Planning Graphs - Needed to take into account that different sub-goals may have different costs of achievement and that there may be interaction of sub-goals - Intuitively the planning graph is a union of literals in the states that can be obtained through forward projection of the search space - This forward projection of literals can be through actions that take preconditions and add their effects to the next level or by persist actions (noops) that say if nothing is done, then the literals are still achievable in the next projection level - Not every subset of literals in a planning graph level are states, but every state at the projection level in search space is a subset of the literals at the level in the planning graph - Projection ceases when the graph levels off (i.e. two consecutive layers are identical) - Extracting heuristics for a state based on the levels of the appearance of the literals in the planning graph can be accomplished by: - Taking the max levels where literals in the state appear (admissible) - Accounts for +ve interactions - Taking the sum of the levels where the literals appear (inadmissible) - We need a way to account for negative interactions .... Mutex relations!