Software that Understands Risks

Tuesday, January 20, 2015 @ 04:01 PM gHale


There is software in development that can give a more accurate picture of arriving at destination B from starting point A, including things like stopping off for lunch in between. The software can give the chance of arriving at the designated time and offer suggestions that can ensure a better chance of arriving at your designated time.

That kind of application is the goal of Brian Williams’ group at MIT’s Computer Science and Artificial Intelligence Laboratory.

RELATED STORIES
Risk Assessment Software Released
Hacking Without the Internet
Need Info? Hack an Exec
Breach: When Minutes Count

At the annual meeting of the Association for the Advancement of Artificial Intelligence (AAAI) this month, researchers in Williams’ group will talk about algorithms that represent significant steps toward “a better Siri” — the user-assistance application found in Apple products.

Together with Williams, Peng Yu and Cheng Fang, who are graduate students in MIT’s Department of Aeronautics and Astronautics, developed software that allows a planner to specify constraints — buses along a certain route should reach their destination at 10-minute intervals — and reliability thresholds, such as 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 stagger 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?

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 end up 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 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.

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.

Both procedures have roots 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 end up 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.



Leave a Reply

You must be logged in to post a comment.