As the world has become more complex, it perhaps stands to reason that we increasingly turn to algorithms to help us plan and coordinate.

In recent years, these algorithms have become more capable, and can factor in uncertainty, such as variations in travel time or erratic communication.

Further emphasis of the capabilities of planning algorithms was provided by a recent paper from researchers at MIT and the Australian National University, which highlights how contingency plans can now be generated automatically should initial plans carry too much risk.

Planning bots

As well as devising these contingency plans, they are also capable of testing the circumstances to determine whether the plans should be enacted.

“The problem with planning contingencies is that there are so many things that can go wrong, if you generated plans for all possible contingencies, you’d go nuts,” the researchers say. “So then the question ends up being, ‘How many contingencies do you generate?'”

In computational terms, the planning process is represented as a graph, with the graph consisting of nodes and edges (think of a network diagram as a representation of such a graph).

Each node is a decision point, with the path then evaluated according to the rewards on offer and the penalties imposed.  The optimum path therefore, is one that maximises reward.

Playing the odds

The next step is to factor in probabilities that make the calculation of reward that much more complicated.  When this is factored in, creating contingency plans can be a huge task.

To make the task manageable, the team used risk thresholds for any particular task.  So for instance, you might be happy with 90% probability in some elements of the task (ie that it works), but 99.9% probability that no humans will be killed in doing the task.

This helped to form a risk budget that the algorithm spends as it tests out various paths.  If a particular path exceeds the budget, the option is removed.

To make the application functional, this process was developed to be almost instantaneous, with heuristics used to speed up proceedings.

Practical applications

The work has some very real and practical applications in planning systems that are capable of updating their plans on the fly whenever new information becomes available.

NASA have already expressed an interest as automated behaviors are a major part of their missions, whether on the surface of asteroids, comets or planetary bodies, or even on missions to outer-planet icy moons like Europa in future.

“Our robotic spacecraft exploring these locales will be challenged to execute their missions efficiently in the presence of significant uncertainty in both their own state and the state of the surrounding environment, while avoiding obstacles and hazards. They will need to appropriately balance accomplishing their scientific and exploration objectives with keeping themselves healthy and out of trouble,” they say.

By developing an automated method of planning the activities of such robotic explorers, they hope that it increases the odds of those missions being a success as it allows mission operators to specify just how conservative or aggressive the craft should be.

What other applications might the planning system have?