Project 5: Symbolic AI Planning

HTN Planning

For this project, we will use the Anytime Pyhop planner.

Pyhop is a hierarchical task network (HTN) planner. To use an HTN planner, one must specify the following:

  • State: Complete description of the current world state. In Pyhop, you can use an arbitrary Python data structure to describe the state.
  • Operators: Each operator describes a state transformation. Operators can optionally include preconditions. If a precondition is not met, the operator will fail. In Pyhop, you will write one Python function for each operator.
  • Methods: Methods encode a planning algorithm that decomposes a task into operators and other methods. In Pyhop, you will write one Python function for each method.

Example

The example below shows a state description of part of the 3rd floor of the M.C. Reynolds building. Several rooms are all connected to a hallway. The lounge is further connected to the copy room. A robot is in room 312 and has not yet visited any other rooms.

# State
state = State('3rd-floor')
state.visited = {'robot': []}
state.loc = {'robot': 'mcrey312'}
state.connected = {'mcrey312': ['hallway', 'mcrey314'], 
                   'hallway': ['mcrey312', 'mcrey314', 'lounge'], 
                   'mcrey314': ['mcrey312', 'hallway'], 
                   'lounge': ['hallway', 'copyroom'], 
                   'copyroom': ['lounge']}

In this example, there is only one operator: go. The go operator moves an entity from one room to an adjacent room, and records the adjacent room as having been visited.

It makes sure the entity is in the starting room and has not already visited the ending room. It also makes sure the rooms are connected.

def go(state, entity, start, end):
    if state.loc[entity] == start and end in state.connected[start] and end not in state.visited[entity]:
        state.loc[entity] = end
        state.visited[entity].append(end)
        return state

There is also only one method in this example. If the start and end are the same, it signals success. If they are connected, it posts as a task the go operator. Otherwise, it posts a list of alternative tasks: travel from start to a neighbor, then recursively post find_route to travel from that neighbor to the end.

def find_route(state, entity, start, end):
    if start == end:
        return TaskList(completed=True)
    elif state.connected[start] == end:
        return TaskList([('go', entity, start, end)])
    else:
        return TaskList([[('go', entity, start, neighbor), ('find_route', entity, neighbor, end)] for neighbor in state.connected[start]])

Anytime Planning

Pyhop employs depth-first search to find a plan. When presented with multiple options, as in the third alternative above, it aggressively makes choices until it has a complete plan. Here is one plan that the planner might produce in response to the task ``:

[('go', 'robot', 'mcrey312', 'mcrey314'), 
 ('go', 'robot', 'mcrey314', 'hallway'), 
 ('go', 'robot', 'hallway', 'lounge'), 
 ('go', 'robot', 'lounge', 'copyroom')]

With properly designed methods, this should produce a plan if one exists, but it is not guaranteed to be the shortest possible plan. If time permits, the planner can go back and try other alternatives, and see if they produce better plans. This is known as anytime planning. Here is an example of a shorter plan:

[('go', 'robot', 'mcrey312', 'hallway'), 
 ('go', 'robot', 'hallway', 'lounge'), 
 ('go', 'robot', 'lounge', 'copyroom')]])

In an anytime planner, a plan is ready to return as soon as the first depth-first search completes. An anytime planner will backtrack and try alternative plans as long as time is available. The multiple options in the third method step above constitute a nondeterministic choice. These nondeterministic choices are the alternatives available to the anytime planner.

Assignment

Custom Domain

Create a planning domain using Pyhop and the Python programming language. One domain must include the following as a minimum:

  • Two distinct types of objects.
  • Three operators.
  • Three methods.
    • At least one of these methods must have another method in its task decomposition.
    • Either that method or a different method must also have a nondeterministic choice in its task decomposition.
  • Two distinct starting states, at least one of which yields a plan containing at least five steps.

Space Exploration

A common use of planning algorithms is in autonomous space exploration. Choose one of two provided space exploration domains: satellite observation and Mars rover coordination. The operators and example problems are provided for you. You must write the methods to make the planner work on the provided examples.

Details

After completing your domains, write a short paper (2-3 pages) containing the following:

  • An introductory paragraph or two describing your target domain and why you initially believed that it was suitable for planning.
  • One to two paragraphs describing how you encoded that domain. Pay particular attention to discussing the tradeoffs involved in the encoding.
    • What domain features are represented explicitly?
    • What domain features have been abstracted away?
    • Why did you perform those abstractions?
    • How good were the plans that were produced?
    • What criteria do you have for “a good plan”?
  • A discussion of your planning strategy for your space exploration domain:
    • What are your methods?
    • What human problem-solving strategies do they embody?
  • A discussion of the performance of your space exploration planner:
    • Run the planner on each domain example problem for five seconds.
    • Create a table:
      • Each row represents a test problem.
      • The columns include:
        • Problem filename
        • Number of distinct plans generated
        • Length of longest plan
        • Length of shortest plan
    • Assess its performance with reference to the data recorded in the table. (If you think any other data is relevant, feel free to add more columns to the table. But your analysis should take all of the above metrics into account at a minimum.)
  • Write a concluding paragraph discussing the utility of planning in general.
    • Under what circumstances is it worthwhile to build and use a planner?
    • When is it not appropriate?
    • Justify your answers based on the experiences in this project you described earlier in the paper.
  • Share with the instructor your GitHub repositories for your custom domain and your space exploration domain.
  • Submit your paper in PDF format via Teams.