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

Researchers at the Massachusetts Institute of Technology (MIT) are developing algorithms that allows a planner to specify constraints and reliability thresholds for a project and is able to assess risk.

01/28/2015


Courtesy: Jose-Luis Olivares, MITImagine 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% 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%.

That kind of application is the goal of Brian Williams' group at MIT's Computer Science and Artificial Intelligence Laboratory—although the same underlying framework has led to software that both NASA and the Woods Hole Oceanographic Institution have used to plan missions.

At the annual meeting of the Association for the Advancement of Artificial Intelligence (AAAI) this month, researchers in Williams' group will present algorithms that represent significant steps toward what Williams described as "a better Siri"—the user-assistance application found in Apple products. But they would be just as useful for any planning task like scheduling flights or bus routes.

Together with Williams, Peng Yu and Cheng Fang, who are graduate students in MIT's Department of Aeronautics and Astronautics, have developed software that allows a planner to specify constraints 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—which 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?

Short tails

One aspect of the software that distinguishes it from previous planning systems is that it assesses risk. "It's always hard working directly with probabilities, because they always add complexity to your computations," Fang said. "So we added this idea of risk allocation. We say, 'What's your budget of risk for this entire mission? Let's divide that up and use it as a resource.'"

The time it takes to traverse any mile of a bus route, for instance, can be represented by a probability distribution—a bell curve, plotting time against probability. Keeping track of all those probabilities and compounding them for every mile of the route would yield a huge computation. But if the system knows in advance that the planner can tolerate a certain amount of failure, it can, in effect, assign that failure to the lowest-probability outcomes in the distributions, lopping off their tails. That makes them much easier to deal with mathematically.

At AAAI, Williams and another of his students, Andrew Wang, have a paper describing how to evaluate those assignments efficiently, in order to find quick solutions to soluble planning problems. But the paper with Yu and Fang—which appears at the same conference session—concentrates on identifying those constraints that prevent a problem's solution.

There's the rub

Both procedures are rooted in graph theory. In this context, 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.

Yu, Williams, and Fang's 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 MIT researchers' system then calculates the lowest-cost way of rebalancing the loop, which it presents to the planner as a modification of the problem's initial constraints.

Massachusetts Institute of Technology (MIT)

web.mit.edu 

- Edited by CFE Media. See more Control Engineering manufacturing IT and MES stories.



No comments
The Engineers' Choice Awards highlight some of the best new control, instrumentation and automation products as chosen by...
The System Integrator Giants program lists the top 100 system integrators among companies listed in CFE Media's Global System Integrator Database.
The Engineering Leaders Under 40 program identifies and gives recognition to young engineers who...
This eGuide illustrates solutions, applications and benefits of machine vision systems.
Learn how to increase device reliability in harsh environments and decrease unplanned system downtime.
This eGuide contains a series of articles and videos that considers theoretical and practical; immediate needs and a look into the future.
Sensor-to-cloud interoperability; PID and digital control efficiency; Alarm management system design; Automotive industry advances
Make Big Data and Industrial Internet of Things work for you, 2017 Engineers' Choice Finalists, Avoid control design pitfalls, Managing IIoT processes
Engineering Leaders Under 40; System integration improving packaging operation; Process sensing; PID velocity; Cybersecurity and functional safety
This article collection contains several articles on the Industrial Internet of Things (IIoT) and how it is transforming manufacturing.

Find and connect with the most suitable service provider for your unique application. Start searching the Global System Integrator Database Now!

SCADA at the junction, Managing risk through maintenance, Moving at the speed of data
Flexible offshore fire protection; Big Data's impact on operations; Bridging the skills gap; Identifying security risks
The digital oilfield: Utilizing Big Data can yield big savings; Virtualization a real solution; Tracking SIS performance
click me