A better ‘Siri’

Planning algorithms evaluate probability of success, suggest low-risk alternatives
January 20, 2015

(Credit: Jose-Luis Olivares/MIT)

At the annual meeting of the Association for the Advancement of Artificial Intelligence (AAAI) this month, MIT computer scientists will present smart algorithms that function as “a better Siri,” optimizing planning for lower risk, such as scheduling flights or bus routes.

They offer this example:

Imagine that you could tell your phone that you want to drive from your house in Boston to a hotel in upstate New York, that you want to stop for lunch at an Applebee’s at about 12:30, and that you don’t want the trip to take more than four hours.

Then imagine that your phone tells you that you have only a 66 percent chance of meeting those criteria — but that if you can wait until 1:00 for lunch, or if you’re willing to eat at TGI Friday’s instead, it can get that probability up to 99 percent.

The new software allows a planner to specify constraints — say, buses along a certain route should reach their destination at 10-minute intervals — and reliability thresholds, such as that the buses should be on time at least 90 percent of the time.

Then, on the basis of probabilistic models that reveal data such as that travel time along this mile of road fluctuates between two and 10 minutes, the system determines whether a solution exists: For example, perhaps the buses’ departures should be staggered by six minutes at some times of day, 12 minutes at others.

If, however, a solution doesn’t exist, the software doesn’t give up. Instead, it suggests ways in which the planner might relax the problem constraints: Could the buses reach their destinations at 12-minute intervals? If the planner rejects the proposed amendment, the software offers an alternative: Could you add a bus to the route?

Graph theory

A directed graph (credit: Wikimedia Commons)

Their algorithms are rooted in graph theory. A graph is a data representation that consists of nodes, usually depicted as circles, and edges, usually depicted as line segments connecting the nodes. Any scheduling problem can be represented as a graph.

Nodes represent events, and the edges indicate the sequence in which events must occur. Each edge also has an associated weight, indicating the cost of progressing from one event to the next — the time it takes a bus to travel between stops, for instance.

The algorithm first represents a problem as a graph, then begins adding edges that represent the constraints imposed by the planner. If the problem is soluble, the weights of the edges representing constraints will everywhere be greater than the weights representing the costs of transitions between events.

Existing algorithms, however, can quickly home in on loops in the graph where the weights are imbalanced. The algorithm then calculates the lowest-cost way of re-balancing the loop, which it presents to the planner as a modification of the problem’s initial constraints.

The open-access papers by the researchers in Brian Williams’ group at MIT’s Computer Science and Artificial Intelligence Laboratory are linked below.

Abstract of Resolving over-constrained probabilistic temporal problems through chance constraint relaxation

When scheduling tasks for field-deployable systems, our solutions must be robust to the uncertainty inherent in the real world. Although human intuition is trusted to balance reward and risk, humans perform poorly in risk assessment at the scale and complexity of real world problems. In this paper, we present a decision aid system that helps human operators diagnose the source of risk and manage uncertainty in temporal problems. The core of the system is a conflict-directed relaxation algorithm, called Conflict-Directed Chance-constraint Relaxation (CDCR), which specializes in resolving overconstrained temporal problems with probabilistic durations and a chance constraint bounding the risk of failure. Given a temporal problem with uncertain duration, CDCR proposes execution strategies that operate at acceptable risk levels and pinpoints the source of risk. If no such strategy can be found that meets the chance constraint, it can help humans to repair the overconstrained problem by trading off between desirability of solution and acceptable risk levels. The decision aid has been incorporated in a mission advisory system for assisting oceanographers to schedule activities in deepsea expeditions, and demonstrated its effectiveness in scenarios with realistic uncertainty.