Practice questions on planning

1. Consider the problem of following paths from one location to another given a graph with vertices corresponding to locations and edges corresponding to roads (or corridors) connecting the locations.
   1. define the predicates you would use to describe the graph. Show an example of an initial state and goal state.
   2. construct an operator using the STRIPS notation from the texbook to move from one location to another given that the two locations are connected.
   3. write an operator similar to the one you just wrote using situational calculus.
   4. comment on advantages and drawbacks of using situational calculus versus using STRIPS operators.
2. Consider the problem of moving one or more objects from a location to another and consider cases in which an object can be carried togheter with another object. For instance, multiple cups on a tray are moved when the tray is moved, an individual cup can also be moved directly.
   • Specify the initial state for a problem in which there is a cup, a plate, and a spoon on a tray, and the tray is on a table. Spcify the goal state for a situation in which the cup and the spoon are on a desk.
   • Define one or more operators for accomplishing the goal you defined above. Make sure the operators allow moving individual objects as well as objects carrying other objects. Define the predicates you use and use the notation for operators defined in the textbook.
   • Can you write the operators using STRIPS-like operators or do you need to extend the planning language? if yes, specify the extensions you need and how they affect the planning algorithm.
   • Suppose you want to generalize the operators to handle more general cases. For instance, a cup on a saucer which is on a tray will be moved when the tray is moved. Will your operators handle this case? If not, can you extend them? How?
3. The POP algorithm includes many non deterministic choices. Consider, in particular, when POP chooses which operator to add to the plan. If POP could select the best operator first, its efficiency would improve. Suggest a domain-independent heuristic for selecting what operator to try first.