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.