# Presentation: 568426

## Planning with Resources at Multiple Levels of Abstraction

- Brad Clement, Tony Barrett, Gregg RabideauArtificial Intelligence GroupJet Propulsion Laboratory
- California Institute of Technology
**{bclement, barrett}@aig.jpl.nasa.gov**

- Ed Durfee
- Artificial Intelligence Lab
- University of Michigan
**durfee@umich.edu**

- Paper to appear in proceedings of ECP-01
- http://ai.eecs.umich.edu/people/bradc

## Motivation

- Hierarchical refinement search can reduce the search space exponentially when there is no need to backtrack up the hierarchy. (Korf ’87, Knoblock ’91)
- Often planning problems have interacting goals such that backtracking is necessary.
- How can this performance advantage be exploited for such problems?
- By summarizing the constraints of an abstract task’s refinement, the planner can reduce the complexity exponentially. (Clement & Durfee 2000)
- How can this work be applied to the use of metric resources?

## Contributions

- Algorithm summarizing metric resource usage for abstract activities based on their decompositions
- Complexity analyses showing that scheduling is exponentially cheaper at higher levels of abstraction using summary information
- Experiments in a multi-rover domain that support the analyses
- Search techniques for directing the refinement of activities in an iterative repair planner that further improve performance

## Resource Usage

- Depletable resource
- usage carries over after end of task
*gas* = *gas* - 5
- Non-depletable
- usage is only local
- zero after end of task
*machines* = *machines* - 2
- Replenishing a resource
- negative usage
*gas* = *gas* + 10
- can be depletable or non-depletable

- interval of task

## Mars Rover

**morning activities**

**move(A, B)**

**sunbathe**

**soak rays****use –4W**
**20 min**

**soak rays****use –5W**
**20 min**

**soak rays****use –6W**
**20 min**

**low path**

**go(A,1)**
**use 6W**
**10 min**

**go(1,2)**
**use 6W**
**10 min**

**go(2,B)**
**use 12W**
**20 min**

**go(A,B)**
**use 8W**
**50 min**

**go(A,3)**
**use 8W**
**15 min**

**go(3,B)**
**use 12W**
**25 min**

**middle path**

**high path**

**A**

**B**

**C**

**D**

**E**

**F**

**1**

**2**

**3**

## Summarizing Resource Usage

**soak rays**

**soak rays**

**soak rays**

**low**

**-4**

**-5**

**-6**

**-4**

**2**

**7**

**0**

**Battery power usage for three possible decompositions**

**6**

**6**

**12**

**2**

**1**

**6**

**-6**

**soak rays**

**soak rays**

**soak rays**

**medium**

**-4**

**-5**

**-6**

**-4**

**0**

**8**

**4**

**3**

**2**

**-6**

**soak rays**

**soak rays**

**soak rays**

**high**

**-4**

**-5**

**-6**

**-4**

**3**

**7**

**0**

**8**

**12**

**4**

**6**

**-6**

## summarized resource usage 
	   < local_min_range, local_max_range, persist_range >

Captures uncertainty of decomposition choices and
temporal uncertainty of partially ordered actions

*	**   **< local_min_range, local_max_range, persist_range >*
- Captures uncertainty of decomposition choices and
- temporal uncertainty of partially ordered actions
*	**	*

- Summarizing Resource Usage

**0**

**40**

**30**

**-7**

**-20**

**20**

**10**

**< [-7, -20],[30, 40],[10, 20] >**

## Resource Summarization Algorithm

- Can be run offline for a domain model
- Run separately for each resource
- Recursive from leaves up hierarchy
- Summarizes parent from summarizations of immediate children
- Considers all legal orderings of children
- Considers all subintervals where upper and lower bounds of children’s resource usage may be reached
- Exponential with number of immediate children, so summarization is really _constant_ for one resource and *O*(*r*) for *r* resources

## Resource Summarization Algorithm

**OR**

- <[0,5][3,6][0,6]>

- <[2,3][3,4][3,4]>

- <[0,5][3,6][0,6]>

## Resource Summarization Algorithm

**Serial AND**

- <[0,5][3,6][0,6]>

- <[2,3][3,4][3,4]>

- <[0,5][3,10][3,10]>

## Resource Summarization Algorithm

**Parallel AND**

- <[0,5][3,6][0,6]>

- <[2,3][3,4][3,4]>

- <[2,9][5,6][3,10]>

## Resource Summarization Algorithm

- for each consistent ordering of endpoints
- for each subtask/subinterval summary usage assignment
- use **Parallel-AND** to combine subtask/subinterval usages by subinterval
- use **Serial-AND** over the chain of subintervals
- use **OR** computation to combine profiles

- Each iterationgenerates a profile

## Complexity Analysis

- Iterative repair planners (such as ASPEN) heuristically pick conflicts and resolve them by moving activities and choosing alternative decompositions of abstract activities.
- Moving an activity hierarchy to resolve a conflict is *O*(*vnc**2*) for *v* state or resource variables, *n* hierarchies in the schedule, and *c* constraints in hierarchy per variable.
- Summarization can collapse the constraints per variable making *c* smaller.
- In the worst case, where no constraints are collapsed because they are over different variables, the complexity of moving and activity hierarchies at different levels of expansion is the same.

**. . .**

**level**

**0**

**1**

***d***

**1**

**2**

***n***

**branching****factor *****b***

***c***** constraints****per hierarchy**

***v*****variables**

## Complexity Analysis

- In the other extreme, where constraints are always collapsed when made for the same variable, the number of constraints *c* is the same as the number of activities and grows *b**i* for *b* children per activity and depth level *i*.  Thus, the complexity of scheduling operations grows *O*(*vnb*2*i*).
- Along another dimension, the number of temporal constraints that can cause conflicts during scheduling grows exponentially (*O*(*b**i*)) with the number of activities as hierarchies are expanded.
- In addition, by using summary information to prune decomposition choices with greater numbers of conflicts, exponential computation is avoided.
**Thus, reasoning at abstract levels can resolve conflicts exponentially faster.**

**. . .**

**level**

**0**

**1**

**d**

**1**

**2**

**n**

**branching****factor b**

***c***** constraints****per hierarchy**

***v*****variables**

## Decomposition Strategies

- Expand most threats first (EMTF)
- instead of moving activity to resolve conflict, decompose with some probability (decomposition rate)
- expands activities involved in greater numbers of conflicts (threats)
- Level expansion
- repair conflicts at current level of abstraction until conflicts cannot be further resolved
- then decompose all activities to next level and begin repairing again
- Relative performance of two techniques depends decomposition rate selected for EMTF

## Decomposition Strategies

- FTF (fewest-threats-first) heuristic tests each decomposition choice and picks those with fewer conflicts with greater probability.

**rover_move**

**path1**

**path2**

**path3**

**10 conflicts**

**20 conflicts**

**15 conflicts**

## Multi-Rover Domain

- 2 to 5 rovers
- Triangulated field of 9 to 105 waypoints
- 6 to 30 science locations assigned according to a multiple travelling salesman algorithm
- Rovers’ plans contain 3 shortest path choices to reach next science location
- Paths between waypoints have capacities for a certain number of rovers
- Rovers cannot be at same location at the same time
- Rovers cannot cannot cross a path in opposite directions at the same time
- Rovers communicate with the lander over a **shared** channel for telemetry--different paths require more bandwidth than others

## Experiments using ASPEN for a Multi-Rover Domain

- Performance improves greatly when activities share a common resource.

**Rarely shared resources (only path variables)**

**Mix of rarely shared (paths) and often shared****(channel) resources**

**Often shared (channel) resource only**

## Experiments using ASPEN for a Multi-Rover Domain

- CPU time required increases dramatically for solutions found at increasing depth levels.

## Picking branches that result in fewer conflicts (FTF) greatly improves performance.

Expanding activities involved in greater numbers of conflictsis better than level-by-level expansion when choosing a proper rate of decomposition

- Expanding activities involved in greater numbers of conflictsis better than level-by-level expansion when choosing a proper rate of decomposition

- Experiments in ASPEN for a Multi-Rover Domain

## Summary

- Algorithm summarizing metric resource usage for abstract activities based on their decompositions
- Complexity analyses showing that scheduling operations are exponentially cheaper at higher levels of abstraction when summarizing activities collapses state/resource constraints and temporal constraints
- Experiments in multi-rover domain support analyses
- Reasoning at abstract levels is wasteful when hierarchies must be fully expanded and OR branch selection is not important
- Search techniques for directing the refinement of activities further improve performance

## Future Work

- How does abstract reasoning affect plan quality using iterative repair?
- How should complex resources be abstracted?
- resource usage functions
- window variables
- geometrical constraints
- volatile objects (file system)
- What is the effect of abstracting over resource classes?
- What are efficient protocols for coordinating a group of agents’ plans continually?