HURON Planner

In the course of our work to study lunar mission scenarios, we have developed a small planning tool called "HUman-Robot Optimization Network" (HURON) with added temporal scheduling support to meet our needs for analysis. Though the name implies our problem domain, we have kept the input problem domain description decoupled with the planning engine itself. Similar to the more recent approaches of heuristics-based graph search, the planner utilizes domain-specific heuristics with a well-proven graph search algorithm. We have very specific domain knowledge that we can (and should) apply to aid the heuristic search even further. Leveraging this domain-specific knowledge can dramatically help not just to prune unnecessary nodes during the search, but also to help direct the search faster towards the goal node.

Planning as search. HURON treats planning as a simple graph search problem in state-space with forward progression. Each node in our search graph contains an instance of a state. Starting with just the initial node, we build an implicit graph with new successive children nodes of new states to explore. Only operators that meet all preconditions are applied to create children states. Then broader-scoped constraints are checked to prune out additional states.

Currently, the search implementation uses the A* algorithm (Nilsson 1980) which is commonly used for searching state-space graphs. When using admissible heuristic, the A* algorithm is admissible and computationally optimal. The A* algorithm combines the benefits of Dijkstra's algorithm with a best-first search algorithm. Dijkstra's algorithm explores the least-cost nodes first, while best-first search tends to favor the more promising nodes closer to the goal. At each node n, the search computes an objective function of the form:

where g(n) is the cost of the path so far, and h(n) is the heuristic estimate of the remaining cost to the goal node. Both g(n) and h(n) is user-provided, along with the input problem domain. Using an open list to track a list of pending nodes to search, and a closed list to track all of the nodes already searched, it visits the next node in the open list with the lowest total f(n) value.

Objective function. Many of the existing planners optimize plans based on the length of operators. However, our application-driven planner requires us to optimize based on different criteria, which may differ problem-by-problem. For some analysis, the objective function may be to minimize operations time. For others, it may be to minimize power consumption.

Productivity. One problem domain objective function we are currently using tries to measure the productivity of an allocation of human-robot activities. The approach uses a definition of productivity that compares the output benefits of each task to the inputs required to perform the tasks. The output benefits are accrued from the accomplishment of science activities (tasks). The inputs are the total costs of completing the tasks in terms of human and robot operating times, and a measure of safety based on distance to account for the risk of astronauts venturing from life-support modules. The use of productivity ("value per cost") to guide the search process provides an allocation of human agents, robot agents, and resources that maximizes value at minimum cost. The tradeoff between value and cost is embedded in every choice made by the automated search to guarantee an optimal solution.

Differences From Other Planners

The Planning Domain Description Language (PDDL) (McDermott 1998) has become the standard exchange language for planning problems. PDDL 2.1 has advanced capabilities such as temporal planning, numeric expressions, conditions and effects. However, there is still some dissatisfaction among the community in terms of the expressiveness of the PDDL language.

System Models. Even with PDDL, there is still a gap (but shrinking) between research-oriented planning problems and real-world applications-driven planning problems. Our lunar studies require the modeling of vehicle systems, astronaut suite, and how they interacted with each other and the environment. When two pressurized elements are air-docked, actions on one element must make sure to act on the two elements as a pair. The language of STRIPS and PDDL, which has roots in first-order calculus, may be not expressive enough for our needs. HURON, being a configurable planner/scheduler with a domain-independent engine, enables us to define domain problems each with its own complex system models and heuristics.

Python. Python is an interpreted, high-level object-oriented programming language that has seen tremendous adoption. Python's flexibility allows it to be used as a simple scripting language on one end, while also being used on full-fledged object-oriented framework development on the other end. HURON was written in Python, which dramatically increased our efficiency of developing new capabilities as needed. We were able to work with faster turnaround in framework development, input-scenario development, and results analysis. Additionally, with the existence of many systems engineering models, using Python enables the ability to both extend and embed with existing legacy code.

Users are not computer scientists. Typical usage of planners in real-world applications involves developing a problem domain and then embedding it into a host application. The embedded planner is called by varying certain parameters or conditions. But for the most part, the problem domain remains the same. For our use, however, the input-problem domain can change quite frequently. New problems must be modeled and run for every new study. The objective functions may be redefined for another analysis run. For this, having a problem-domain-description approach that is easier for our users to use is crucial. The Lisp-like syntax of PDDL/STRIPS may not be the easiest format for users who are not oriented toward computer science.

Problem description. To simplify usage and increase expressiveness, HURON's problem-domain-description language is full Python. Operators, constraints, and the entities of a problem domain are all defined as Python classes. Instead of defining fluents in Lisp-like form, operators can contain the more naturally understood formalisms of Python. Entities, which are also classes, can leverage the notion of subclassing implementations and reusing problem domains. This approach enables us to define action durations that are dynamically computed. For our user base, which includes systems engineers, using Python has been a tremendous help in having users being able to quickly write and run their own planning problems.

Software Architecture. With the input problem description and the planning framework written in Python, all components are developed as classes organized by Python modules. Even though written with an interpreted language, this approach still mirrors how Java and .NET frameworks are developed.

The input problem domain includes the definition of all entities, operators, and constraints. Users would also provide the domain-specific path cost g(n) and heuristic h(n) functions that the A* search algorithm will use to find the optimal plan. The usage of Python facilitates convenient modifications to the user-defined objective functions, enabling users to change what is being optimized.

The search module also includes the Observer design pattern (Gamma et al. 1995) to enable listeners to dynamically register interests to the search process itself. This has proven to be very useful for us for generating a multitude of output data used for analysis.

Output. Microsoft Excel has been a dominant platform for most JPL system engineers; many of the instrument models have been developed using Excel and Visual Basic. By using pyExcelerator (pyExcelerator 2008) and writing listeners for the search module, we were able to generate binary Excel files containing the full search trail of actions along with each step's state data and its corresponding f, g, and h values. We wrote additional search listeners to generate schedules in Excel of the result in a timeline format (Figure 1). The state-by-state data was also exported to leverage Excel's more powerful plotting capabilities.

Figure 1. Generated Excel showing scheduled timeline. Full data is also in worksheet-enabling plots to be generated by Excel.

To help visualize the search process, another search listener was developed that generated the search states in Graphviz's (Gansner & North 1999) *.dot format. Graphviz enabled us to graphically visualize the search graph and to visualize cycles in the search process. Figure 2 shows that subgraphs can also be identified in the search, indicative of a choice in the plan that led to a grouping of consequences. This was useful in identifying potential pruning through logical changes in the operators and constraints.

Scheduling. Temporal support was added to the planner, utilizing some principles discussed in the PDDL 2.1 language with extensions for temporal planning (Fox 2003). Actions are viewed as having discrete points where it begins and ends. For PDDL 2.1, durative actions appear in the plan as also having a duration defined by a real number. However, for our needs we represent time using a full date/time object, while durations are represented as time delta objects. This enables us to perform temporal arithmetic such as adding/subtracting arbitrary time deltas to date/times. The benefit of this approach is evident when a problem domain requires calendar-specific events.

Figure 2. An example search graph showing the nodes searched, cycles detected, and the optimal path of the solution. Subgraphs are visible with loosely connected paths.

Similar to other temporal planners, our approach restricts the temporal placement of actions at time epochs defined by the discrete times of each action. Simple concurrency is supported by the placement of each agent's actions onto a timeline. That is, by extracting what temporal entities participate in each durative action, we can schedule the appropriate action for each participating agent on a timeline.

Application to Human-Robot Lunar Activity Optimization

We faced several challenges in working with a planner for analysis of lunar mission scenarios.

Knowledge domain. Lunar mission planning requires specialized domain knowledge. Without specific details of the knowledge domain, it would be more difficult to accurately model the planning aspects of the problem we are trying to optimize. This knowledge integration has been addressed as one of the main issues with deploying planning software to the real world (Castillo 2007). Developing a more accurate planning problem would then require the domain experts to contribute to the construction of the problem definition itself. We met with a geologist from NASA's lunar architecture team who pointed out that much of the geological fieldwork will be collecting information about the rock formations and constructing an ongoing understanding of the geological history of that site region (Eppler 2004).

Performance. Being a high-level interpreted language, Python is many times slower than C/C++. However, for our purposes, the high-performance was not as importance as the gains in flexibility of expression and faster development turnaround that Python provides. Nonetheless, there are still some things that can be done to minimize the overhead of Python.

We use Psyco (Rigo 2004), a Python extension module that can speed up the execution of interpreted Python code. It implements the novel techniques of just-in-time specialization and representations that reduces the interpretive overhead. Though the module is documented to have speedups of 2X-100X for other codes, we experienced about 30% increase in performance by using psyco. But this varied depending also on the domain problems being run.

We were also able to speed up the performance of the A* search algorithm using certain data structures for the open and closed list of nodes. The open list of nodes stores a list of pending nodes yet to search. The A* algorithm needs to select the node with the lowest total f(n) value to explore next. Rather than keeping the list of nodes fully sorted, a binary min heap is used which has the characteristic that the minimum value node is always at the root of its binary tree structure. Heaps support accessing, inserting, and removing of the minimum value node in O(log n) time per update (Skiena 1990). Without a heap, keeping a sorted list of open nodes proportionally slows down as the graph search size increases.

The A* algorithm uses a closed list to store the nodes that have already been visited. However, we must frequently search through this list to check whether a current state is one that is semantically equivalent to one that we have already visited. Therefore, a comparison of states must be made for each state in the closed list. This process can be made more efficient by using a hash table for the closed list that stores states associated with a lookup key. Hash tables support efficient O(1) on average for insertion and retrieval. Python's C implementation uses a heavily optimized hash table with collision resolution, and we want to leverage it. For each state, we construct a string representation of the state, which is then used by a Secure Hash Algorithm (SHA)-1 algorithm (FIPS 180-2) to generate a key for fast state lookup.

Memory. Searching in state-space requires that each node contain a full instance of the state object. The A* algorithm requires that we store all of the states visited in addition to all of the states pending. Together this can consume large amounts of memory, and for large problems we can frequently run out of memory. In these scenarios, a good heuristic and guidance heuristics become crucial for faster and more informed search. Another possible approach to address the large memory issues is to add a new search module that implements the Iterative Deepening-A* algorithm or Memory-bounded A*. These variations trade memory for more computation.

Heuristic cost estimation. Using A* requires the construction of a heuristic h(n) function used to estimate the remaining costs from the current node to the goal node. However, our approach relies on a domain-specific estimation that must be provided for each class of problems. The challenge involves ensuring that the h(n) heuristic estimate remains admissible-that is, it never overestimates the actual minimum cost of reaching the goal. Additionally, the heuristic estimate provided by the problem domain must also be monotonic (or consistent) for A* to be optimal. The estimate should not decrease in any path from the initial state.

More recent approaches utilize domain-independent heuristics. The Greedy Regression Tables (GRT) Planning System (Refanidis 2001), for example, utilizes a domain-independent heuristic and applied it to its STRIPS world paradigm.

Optimizing versus sufficing. Though the A* algorithm is great for finding the optimal path, it does not generate iteratively better solutions. For times when a goal is not found quickly enough, or when we run out of memory during a search, even a non-globally optimal solution will suffice. But for the original A* implementation, it will either yield the optimal solution or none at all. Since it is a form of best-first search, stopping the search mid-way will only yield the best incomplete sequence of actions found so far.

Relevant work

Various related works have been published covering different aspects of the planning and scheduling problems. Our lunar task optimization problem must optimize the task allocation and scheduling with multiple agents. A subset of this problem may include optimizing the best route path of lunar site locations. Each agent may potentially have a different set of capabilities, but they all must collaborate to achieve a common goal.

Without an emphasis on path routing, Tompkins (2003) has shown a Mixed Integer-Linear Programming (MILP) approach and a Multiple Objective Linear Programming approach (MOLP) to solving multiagent task allocation and scheduling problems. However, the approach was noted to take exponential time, and thus is practical for limited numbers of agents and tasks.

HURON's real-world applications-driven development has requirements similar to NASA ARC's EUROPA temporal planner. EUROPA was designed to support planning for complex systems such as spacecraft and rovers, and is typically embedded in a host application (Frank & Jonsson 2003). For input, it uses a custom object-oriented language called New Domain Description Language (NDDL) to define problem domains. HURON uses the standard Python object-oriented language for defining the problem domain. EUROPA maps the planning problem to a Dynamic Constraint Satisfaction Problem (DCSP) to be solved.

Conclusion

The study of lunar mission architectures requires the capability to conveniently define multiple domain problem scenarios for planning and scheduling analysis. We have found that a useful planner is one that enables us to easily define new domain problems, custom-configure objective functions, and perform varying runs. Analysis of human-robot task allocations for lunar missions also requires more-complex systems modeling capabilities than traditional PDDL/STRIPS formats can currently offer. These unique aspects of our analysis needs led us to develop a planning framework that forgoes high-performance and PDDL syntax in exchange for the added flexibility of input and usage. However, by not utilizing the propositional formalisms of STRIPS or PDDL, we cannot directly leverage the advantages of research in that area. Unlike some planning tools that are commonly embedded into a host application, our typical usage requires us to run and rerun scenarios by varying aspects of the problem such as the objective function. Our user base is not computer scientists, and this drove the need to enable a more user-friendly problem-domain-definition format that is based on the popular Python language, giving users the ability to quickly define their own planning problems and vary their analysis. The usage of Python and the A* algorithm for planning comes with performance and memory overhead which can be alleviated with some techniques. The usage of problem-specific domain knowledge and heuristics from the domain experts can also improve the search process.