MIT's Planning Algorithms are Like Siri, Except Creative and Helpful

Illustration: iStockphoto

People have trouble with realistic planning. By “people,” I mean humans in general, particularly those of us who have jobs and families and hobbies and all that other stuff that makes life variable and complicated. We can’t do it all, but we try anyway, and it frequently involves failures of varying levels of catastrophe. While there are plenty of interactive tools to assist us with scheduling, they mostly just do what we say, whether or not it makes sense. MIT engineers are trying to inject some sense into personal planning. They are trying to make a better version of Apple’s Siri virtual assistant by factoring in risks and probabilities of success, and offering alternatives, even if those alternatives bend the rules a little bit.

To get a sense of how a planning algorithm could be even a little bit cool, consider this travel scenario. Say you’re planning on traveling from Seattle to Portland for a dinner meeting. You’ll need to rent a car, make a reservation at a restaurant, find a hotel for the night, and then be back in Seattle by noon the next day, all while keeping your travel budget in mind. What MIT’s algorithms can do is consider all of these variables (along with others like hotel ratings, what food you like, and so on), and then come up with an itinerary that will work.

Of course, just coming up with an itinerary is not a unique capability. What is unique is that MIT’s algorithms (called a “decision aid” in practice) understand when what you’re asking for just isn’t likely to happen, and then suggest ways to fix it. In our scenario above, maybe the train you’re planning on taking is often late. In that case, the algorithm would tell you, “hey, if you take this train, you might miss your meeting. If you fly instead, you’re more likely to make it.”

The algorithm can also suggest ways to bend the rules a little more: maybe increasing your budget could get you on a different train that would increase your chances of arriving on time. You can then tell the algorithm that your budget can’t change, and it might instead suggest a less fancy hotel than you’d asked for, or pushing back the meeting time. Basically, it gets creative.

Here’s another (slightly more technical) example from the MIT paper to be delivered at next weeks Association for the Advancement of Artificial Intelligence conference:

A scientist is planning to deploy an underwater robot to survey a volcano eruption on the sea floor. The eruption will occur at around 10:00, following a normal distribution with a variance of 30 minutes. It is 8:00 now, and the robot needs to arrive at the site before the start of the eruption. In addition, at least 45 minutes is required for traversing to the site, and 30 minutes for collecting samples. The scientist wants the mission to complete in 3 hours, with less than 5% risk of violating any constraints, such as being late or missing the event. After evaluating all the requirements, the decision aid (DA) determines that no solution exists that meets all requirements. It immediately engages the scientist (ST) and initiates a discussion to resolve this problem.

DA: I cannot meet all requirements due to the limited mission
time and the uncertainty in eruption. Can you extend
the mission to 4 hours and 10 minutes.
ST: You can have at most 4 hours for this mission.
DA: May I increase the risk bound for this mission to
7.3% in order to meet the duration requirement?
ST: I do not want to take that much risk on this task.
DA: Ok, can you shorten the traversal time from the site
to the ship by 6 minutes? My plan can then cover 95% of the
possible eruption time, between 8:45 and 10:51.
ST: That’s fine. Thanks.

To make all of this work, the algorithm gathers as much information as it can to calculate risk (probability of success) and then uses risk as a budgeted resource. This allows it to minimize risk if that’s what you want, or at the very least, be aware of exactly how risky your plan is. Also, being able to quantify risk makes it possible to see how small changes to parts of a plan dynamically effect the probablility of success of the plan as a whole.

Scheduling problems like the two example above can be represented mathematically as graphs, with nodes (events) connected by lines (constraints), with each line also representing the cost of transitioning from one event to another. MIT’s algorithm is able to efficiently balance constraints and transitions if possible, and if it finds that the existing graph can’t be solved, it then calculates the easiest possible way of rebalancing the graph by modifying a constraint.

This algorithm has already been used in oceanography for management of multiple robots manage multiple robots performing several week long missions over multiple sites where ocean currents introduce a lot of uncertainty. If it can work in situations like that, it seems like it should be ready to tackle problems which are only marginally more complicated, like my typical Thursday afternoon.


Tech Talk

IEEE Spectrum’s general technology blog, featuring news, analysis, and opinions about engineering, consumer electronics, and technology and society, from the editorial staff and freelance contributors.

Newsletter Sign Up

Sign up for the Tech Alert newsletter and receive ground-breaking technology and science news from IEEE Spectrum every Thursday.