Software That Suggests Low-risk Alternatives
January 16, 2015Imagine 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 smart 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. The 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) in January 2014, researchers in Williams' group present algorithms that represent steps toward what Williams describes as "a better Siri," the user-assistance application found in Apple products.
MIT researchers have developed software that 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% 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 2- 10 minutes -- the system determines whether a solution exists. For example, perhaps the buses' departures should be staggered by 6 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. 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.
Question or comment on this article? Contact an editor: engineering360editors@ihs.com