Planning software: new algorithm computes and adjusts your constraints

By February 26, 2015
Planning software: new algorithm computes and adjusts your constraints

A professor and two graduate students at MIT’s Department of Aeronautics and Astronautics are developing a software programme which can assess the percentage chance of success of completing an itinerary on time and suggest adjustments.

How can you work out your realistic chances of getting from point A to point B without a hitch? This is the principle behind the Personal Transportation System programme (PTS) being developed by Brian Williams, Peng Yu and Cheng Fang from the Massachusetts Institute of Technology (MIT). They presented a paper entitled ‘Resolving Over-Constrained Probabilistic Temporal Problems through Chance Constraint Relaxation’ at the annual meeting of the Association for the Advancement of Artificial Intelligence (AAAI) in January. Their algorithm-based software programme facilitates the planning of all kinds of itineraries taking into account the risks of failure peculiar to each. Based on probability modelling, the algorithm assesses the percentage chance of a journey being completed as planned, given the user’s stated goals plus constraints such as budget, timescale and potential stops to take a break, eat, pick up colleagues or equipment, etc. The advice it provides is therefore much more sophisticated than a simple GPS system. When the software reckons your chances of completing your journey on time are too low it will put forward alternative solutions, which take your wishes into account but might suggest reducing or adjusting certain demands so as to achieve a higher probability of success.

Proposing alternative solutions

The algorithm is based on a weighted graph, a mathematical construct common in computer science. The graph represents events as nodes, which are tied together by links, in the order that the events are supposed to occur. Where needed, the software will work out alternative solutions that still meet the user’s basic requirements while avoiding the plan becoming “over-constrained”. The use of weighted graphs enables the programme to work out the smallest possible change of plan consistent with a high probability of meeting your deadline. The algorithm’s ability to take into account potential constraints and allocate a risk level to each by using the graphs means that the advice the system gives you is more realistic than other currently available planning software is able to provide, claim the MIT team.

Transforming planning tools in various fields

What is most innovative about the MIT system is that it essentially sets up a dialogue between user and system. The user explains his/her objectives and constraints in terms of time, budget, etc to the programme and then just has to wait for the software’s  verdict on the adjustments s/he may have to make to the original planning. The system, described by its creators as "a better Siri" – referring to the Apple personal assistant/ knowledge navigator app – can be applied in far-flung fields way beyond the domestic sphere and looks set to revolutionise our entire approach to planning software. Both the US National Aeronautics and Space Administration (NASA) and the Woods Hole Oceanographic Institution are already using a similar approach to plan their complex multi-year missions and give themselves the best possible chance of meeting their deadlines. So how long will it be before our smartphones acquire the ability to take decisions for us?

Legal mentions © L’Atelier BNP Paribas