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

## Siri, Cortana, and other virtual assistants are good at doing what you tell them, but MIT's algorithms could make them clever on their own

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.

The Conversation (0)

## Why Functional Programming Should Be the Future of Software Development

### It’s hard to learn, but your code will produce fewer nasty surprises

Vertical
Shira Inbar
DarkBlue1

You’d expectthe longest and most costly phase in the lifecycle of a software product to be the initial development of the system, when all those great features are first imagined and then created. In fact, the hardest part comes later, during the maintenance phase. That’s when programmers pay the price for the shortcuts they took during development.

So why did they take shortcuts? Maybe they didn’t realize that they were cutting any corners. Only when their code was deployed and exercised by a lot of users did its hidden flaws come to light. And maybe the developers were rushed. Time-to-market pressures would almost guarantee that their software will contain more bugs than it would otherwise.

The struggle that most companies have maintaining code causes a second problem: fragility. Every new feature that gets added to the code increases its complexity, which then increases the chance that something will break. It’s common for software to grow so complex that the developers avoid changing it more than is absolutely necessary for fear of breaking something. In many companies, whole teams of developers are employed not to develop anything new but just to keep existing systems going. You might say that they run a software version of the Red Queen’s race, running as fast as they can just to stay in the same place.

It’s a sorry situation. Yet the current trajectory of the software industry is toward increasing complexity, longer product-development times, and greater fragility of production systems. To address such issues, companies usually just throw more people at the problem: more developers, more testers, and more technicians who intervene when systems fail.

Surely there must be a better way. I’m part of a growing group of developers who think the answer could be functional programming. Here I describe what functional programming is, why using it helps, and why I’m so enthusiastic about it.

## With functional programming, less is more

A good way to understand the rationale for functional programming is by considering something that happened more than a half century ago. In the late 1960s, a programming paradigm emerged that aimed to improve the quality of code while reducing the development time needed. It was called structured programming.

Various languages emerged to foster structured programming, and some existing languages were modified to better support it. One of the most notable features of these structured-programming languages was not a feature at all: It was the absence of something that had been around a long time— the GOTO statement.

The GOTO statement is used to redirect program execution. Instead of carrying out the next statement in sequence, the flow of the program is redirected to some other statement, the one specified in the GOTO line, typically when some condition is met.

The elimination of the GOTO was based on what programmers had learned from using it—that it made the program very hard to understand. Programs with GOTOs were often referred to as spaghetti code because the sequence of instructions that got executed could be as hard to follow as a single strand in a bowl of spaghetti.

Shira Inbar

The inability of these developers to understand how their code worked, or why it sometimes didn’t work, was a complexity problem. Software experts of that era believed that those GOTO statements were creating unnecessary complexity and that the GOTO had to, well, go.

Back then, this was a radical idea, and many programmers resisted the loss of a statement that they had grown to rely on. The debate went on for more than a decade, but in the end, the GOTO went extinct, and no one today would argue for its return. That’s because its elimination from higher-level programming languages greatly reduced complexity and boosted the reliability of the software being produced. It did this by limiting what programmers could do, which ended up making it easier for them to reason about the code they were writing.

Although the software industry has eliminated GOTO from modern higher-level languages, software nevertheless continues to grow in complexity and fragility. Looking for how else such programming languages could be modified to avoid some common pitfalls, software designers can find inspiration, curiously enough, from their counterparts on the hardware side.

## Nullifying problems with null references

In designing hardware for a computer, you can’t have a resistor shared by, say, both the keyboard and the monitor’s circuitry. But programmers do this kind of sharing all the time in their software. It’s called shared global state: Variables are owned by no one process but can be changed by any number of processes, even simultaneously.

Now, imagine that every time you ran your microwave, your dishwasher’s settings changed from Normal Cycle to Pots and Pans. That, of course, doesn’t happen in the real world, but in software, this kind of thing goes on all the time. Programmers write code that calls a function, expecting it to perform a single task. But many functions have side effects that change the shared global state, giving rise to unexpected consequences.

In hardware, that doesn’t happen because the laws of physics curtail what’s possible. Of course, hardware engineers can mess up, but not like you can with software, where just too many things are possible, for better or worse.

Another complexity monster lurking in the software quagmire is called a null reference, meaning that a reference to a place in memory points to nothing at all. If you try to use this reference, an error ensues. So programmers have to remember to check whether something is null before trying to read or change what it references.

Nearly every popular language today has this flaw. The pioneering computer scientist Tony Hoare introduced null references in the ALGOL language back in 1965, and it was later incorporated into numerous other languages. Hoare explained that he did this “simply because it was so easy to implement,” but today he considers it to be a “billion-dollar mistake.” That’s because it has caused countless bugs when a reference that the programmer expects to be valid is really a null reference.

Software developers need to be extremely disciplined to avoid such pitfalls, and sometimes they don’t take adequate precautions. The architects of structured programming knew this to be true for GOTO statements and left developers no escape hatch. To guarantee the improvements in clarity that GOTO-free code promised, they knew that they’d have to eliminate it entirely from their structured-programming languages.

History is proof that removing a dangerous feature can greatly improve the quality of code. Today, we have a slew of dangerous practices that compromise the robustness and maintainability of software. Nearly all modern programming languages have some form of null references, shared global state, and functions with side effects—things that are far worse than the GOTO ever was.

How can those flaws be eliminated? It turns out that the answer has been around for decades: purely functional programming languages.

Of the top dozen functional-programming languages, Haskell is by far the most popular, judging by the number of GitHub repositories that use these languages.

The first purely functional language to become popular, called Haskell, was created in 1990. So by the mid-1990s, the world of software development really had the solution to the vexing problems it still faces. Sadly, the hardware of the time often wasn’t powerful enough to make use of the solution. But today’s processors can easily manage the demands of Haskell and other purely functional languages.

Indeed, software based on pure functions is particularly well suited to modern multicore CPUs. That’s because pure functions operate only on their input parameters, making it impossible to have any interactions between different functions. This allows the compiler to be optimized to produce code that runs on multiple cores efficiently and easily.

As the name suggests, with purely functional programming, the developer can write only pure functions, which, by definition, cannot have side effects. With this one restriction, you increase stability, open the door to compiler optimizations, and end up with code that’s far easier to reason about.

But what if a function needs to know or needs to manipulate the state of the system? In that case, the state is passed through a long chain of what are called composed functions—functions that pass their outputs to the inputs of the next function in the chain. By passing the state from function to function, each function has access to it and there’s no chance of another concurrent programming thread modifying that state—another common and costly fragility found in far too many programs.

### Avoiding Null-Reference Surprises

A comparison of Javascript and Purescript shows how the latter can help programmers avoid bugs.

Functional programming also has a solution to Hoare’s “billion-dollar mistake,” null references. It addresses that problem by disallowing nulls. Instead, there is a construct usually called Maybe (or Option in some languages). A Maybe can be Nothing or Just some value. Working with Maybes forces developers to always consider both cases. They have no choice in the matter. They must handle the Nothing case every single time they encounter a Maybe. Doing so eliminates the many bugs that null references can spawn.

Functional programming also requires that data be immutable, meaning that once you set a variable to some value, it is forever that value. Variables are more like variables in math. For example, to compute a formula, y = x2 + 2x – 11, you pick a value for x and at no time during the computation of y does x take on a different value. So, the same value for x is used when computing x2 as is used when computing 2x. In most programming languages, there is no such restriction. You can compute x2 with one value, then change the value of x before computing 2x. By disallowing developers from changing (mutating) values, they can use the same reasoning they did in middle-school algebra class.

Unlike most languages, functional programming languages are deeply rooted in mathematics. It’s this lineage in the highly disciplined field of mathematics that gives functional languages their biggest advantages.

Why is that? It’s because people have been working on mathematics for thousands of years. It’s pretty solid. Most programming paradigms, such as object-oriented programming, have at most half a dozen decades of work behind them. They are crude and immature by comparison.

Imagine if every time you ran your microwave, your dishwasher’s settings changed from Normal Cycle to Pots and Pans. In software, this kind of thing goes on all the time.

Let me share an example of how programming is sloppy compared with mathematics. We typically teach new programmers to forget what they learned in math class when they first encounter the statement x = x + 1. In math, this equation has zero solutions. But in most of today’s programming languages, x = x + 1 is not an equation. It is a statement that commands the computer to take the value of x, add one to it, and put it back into a variable called x.

In functional programming, there are no statements, only expressions. Mathematical thinking that we learned in middle school can now be employed when writing code in a functional language.

Thanks to functional purity, you can reason about code using algebraic substitution to help reduce code complexity in the same way you reduced the complexity of equations back in algebra class. In non-functional languages (imperative languages), there is no equivalent mechanism for reasoning about how the code works.

## Functional programming has a steep learning curve

Pure functional programming solves many of our industry’s biggest problems by removing dangerous features from the language, making it harder for developers to shoot themselves in the foot. At first, these limitations may seem drastic, as I’m sure the 1960s developers felt regarding the removal of GOTO. But the fact of the matter is that it’s both liberating and empowering to work in these languages—so much so that nearly all of today’s most popular languages have incorporated functional features, although they remain fundamentally imperative languages.

The biggest problem with this hybrid approach is that it still allows developers to ignore the functional aspects of the language. Had we left GOTO as an option 50 years ago, we might still be struggling with spaghetti code today.

To reap the full benefits of pure functional programming languages, you can’t compromise. You need to use languages that were designed with these principles from the start. Only by adopting them will you get the many benefits that I’ve outlined here.

But functional programming isn’t a bed of roses. It comes at a cost. Learning to program according to this functional paradigm is almost like learning to program again from the beginning. In many cases, developers must familiarize themselves with math that they didn’t learn in school. The required math isn’t difficult—it’s just new and, to the math phobic, scary.

More important, developers need to learn a new way of thinking. At first this will be a burden, because they are not used to it. But with time, this new way of thinking becomes second nature and ends up reducing cognitive overhead compared with the old ways of thinking. The result is a massive gain in efficiency.

But making the transition to functional programming can be difficult. My own journey doing so a few years back is illustrative.

I decided to learn Haskell—and needed to do that on a business timeline. This was the most difficult learning experience of my 40-year career, in large part because there was no definitive source for helping developers make the transition to functional programming. Indeed, no one had written anything very comprehensive about functional programming in the prior three decades.

To reap the full benefits of pure functional programming languages, you can’t compromise. You need to use languages that were designed with these principles from the start.

I was left to pick up bits and pieces from here, there, and everywhere. And I can attest to the gross inefficiencies of that process. It took me three months of days, nights, and weekends living and breathing Haskell. But finally, I got to the point that I could write better code with it than with anything else.

When I decided that our company should switch to using functional languages, I didn’t want to put my developers through the same nightmare. So, I started building a curriculum for them to use, which became the basis for a book intended to help developers transition into functional programmers. In my book, I provide guidance for obtaining proficiency in a functional language called PureScript, which stole all the great aspects of Haskell and improved on many of its shortcomings. In addition, it’s able to operate in both the browser and in a back-end server, making it a great solution for many of today’s software demands.

While such learning resources can only help, for this transition to take place broadly, software-based businesses must invest more in their biggest asset: their developers. At my company, Panoramic Software, where I’m the chief technical officer, we’ve made this investment, and all new work is being done in either PureScript or Haskell.

We started down the road of adopting functional languages three years ago, beginning with another pure functional language called Elm because it is a simpler language. (Little did we know we would eventually outgrow it.) It took us about a year to start reaping the benefits. But since we got over the hump, it’s been wonderful. We have had no production runtime bugs, which were so common in what we were formerly using, JavaScript on the front end and Java on the back. This improvement allowed the team to spend far more time adding new features to the system. Now, we spend almost no time debugging production issues.

But there are still challenges when working with a language that relatively few others use—in particular, the lack of online help, documentation, and example code. And it’s hard to hire developers with experience in these languages. Because of that, my company uses recruiters who specialize in finding functional programmers. And when we hire someone with no background in functional programming, we put them through a training process for the first few months to bring them up to speed.

## Functional programming’s future

My company is small. It delivers software to governmental agencies to enable them to help veterans receive benefits from the U.S. Department of Veteran’s Affairs. It’s extremely rewarding work, but it’s not a lucrative field. With razor-slim margins, we must use every tool available to us to do more with fewer developers. And for that, functional programming is just the ticket.

It’s very common for unglamorous businesses like ours to have difficulty attracting developers. But we are now able to hire top-tier people because they want to work on a functional codebase. Being ahead of the curve on this trend, we can get talent that most companies our size could only dream of.

I anticipate that the adoption of pure functional languages will improve the quality and robustness of the whole software industry while greatly reducing time wasted on bugs that are simply impossible to generate with functional programming. It’s not magic, but sometimes it feels like that, and I’m reminded of how good I have it every time I’m forced to work with a non-functional codebase.

One sign that the software industry is preparing for a paradigm shift is that functional features are showing up in more and more mainstream languages. It will take much more work for the industry to make the transition fully, but the benefits of doing so are clear, and that is no doubt where things are headed.

This article appears in the December 2022 print issue as “A New Way to Squash Bugs.”