Task Scheduling

How might NASA systematically approach the assignment of tasks to astronauts and robots on the Moon?

NASA's Vision for Space Exploration calls for returning astronauts to the Moon in preparation for human missions to Mars and beyond. On the Moon, astronauts would gain experience in using local resources (e.g., lunar soil and lunar water ice if it exists) and in working with robots and other equipment to accomplish their tasks.

The Directorate Integration Office of NASA's Exploration Systems Mission Directorate asked the START team to develop and apply a system for optimizing scenarios in which astronauts and robots accomplish a group of activities on the Moon. We created an automated planning tool, dubbed HURON (for HUman-Robot Optimization Network), and a system for using it. Together, they can be an extremely helpful asset to NASA decision-makers seeking (1) to optimize the distribution of activities between astronauts and robots engaged in scientific pursuits on the lunar surface (or any other location), and (2) to schedule these activities in the most efficient order. Unlike many of the large-scale planners discussed in the literature, the START approach is independent of any specific problem and gives the user freedom to specify agents, actions, resources, parameters, constraints, start and goal states and the objective function to be optimized.

We are conducting an ongoing series of studies which provide a good illustration of the iterative nature of our methodology. The results of any given study can enhance the decision-makers' understanding of the problem they want to solve, leading them to modify their inputs for the next study. As the series of studies progresses, the model they address increasingly improves. Both the optimization system and the mission scenarios have been evolving due to this dynamic.

Even with the relatively uncomplicated problems considered in the first two studies, the number of possible combinations of agents, resources, and activities led to a large number of nodes to be explored, as illustrated below. Heuristics ("rules of thumb" to guide the choices of the planner algorithm) needed to be developed to enable the planner to reach its solution in a manageable amount of time.

Illustration of rapidly expanding search space.

Case Studies: Allocating Tasks 1 Allocating Tasks 2 Comparing Architectures: Pressurized vs. Unpressurized Rovers