Take it from US Air Force Captain Kyle McAlpin when he says that scheduling C-17 aircraft crews is a headache. An artificial intelligence (AI) research flight commander for the Department of Air Force–MIT AI Accelerator Program, McAlpin is also an experienced C-17 pilot. “You could have a mission change and spend the next 12 hours of your life rebuilding a schedule that works,” he says.
It’s a pain point for crew of 52 squadrons who operate C-17s, the military cargo aircraft that transport troops and supplies globally. This year, the Air Force marked 4 million flight hours for its C-17 fleet, which comprises 275 US and allied aircraft. Each flight requires scheduling a crew of six on average, though crew requirements vary depending on the mission.
“Being a scheduler is an additional duty on top of an airman’s main job, such as being a pilot,” says Capt. Ronisha Carter, a Cyberspace Operations officer and the primary airman on a research team spanning the Department of the Air Force (DAF), the MIT Department of Aeronautics and Astronautics, and MIT Lincoln Laboratory. “What we want is for a scheduler to click a button, and an optimal schedule is created.”
Collaborating with their Air Force sponsor organization, Tron, the team has developed an AI-enabled plugin for the existing C-17 scheduling tool to fulfill that vision. The software plugin automates C-17 aircrew scheduling and optimizes crew resources, and was developed as part of the DAF–MIT AI Accelerator partnership.
Nearly 7,600 airmen are poised to use the technology once it is rolled out this summer. It is being integrated into the scheduling software, called Puckboard, that C-17 airmen currently use to build schedules two weeks in advance. Prior to Puckboard’s development in 2019, the squadrons had been using whiteboards and spreadsheets to manually plan out schedules. While Puckboard was a major improvement to the paper and pen, it didn’t have the “brains of optimization algorithms” to help schedulers avoid the mentally draining aspects of the task, says Michael Snyder, a software engineer and team lead in the AI Software Architectures and Algorithms Group at MIT Lincoln Laboratory.
The airmen have many factors to consider as they build the schedules. When is air space available? Who is available to fly given rest requirements, deployments, and vacations? From that subset of available pilots, who is qualified? Some pilots, for example, may not be certified for night flying or air refueling. It’s also up to the scheduler to book training flights to keep pilots qualified in these areas.
“You have a lot of data and factors and the information is so spread out. It’s not something a human being can do in an efficient manner, and the decisions they come to might not make the most efficient use of resources. That’s where AI plays a role,” says Hamsa Balakrishnan, who is the William E. Leonhard Professor of Aeronautics and Astronautics at MIT and principal investigator of the program.
The team’s approach to solving this scheduling problem fuses two techniques. The first is integer programming. In this approach, the algorithm solves an optimization problem by using binary (yes or no) decisions to decide whether or not to assign a pilot to an event. An optimal solution maximizes the values assigned to the desired characteristics of a “good” schedule. Among the many desired characteristics, examples include increasing the rate at which pilots make progress toward satisfying their training requirements, or not unnecessarily assigning personnel to a flight who are significantly overqualified for the task at hand.
Candidate schedules with pilot assignments are then presented to an airman (or an automatic agent), who can accept or reject a schedule. Each time a schedule is accepted, the algorithm is rewarded for its choices, which allows it to recognize successful patterns and improve its decisions over time. This process is called reinforcement learning.
Training the model has required feeding it a lot of historical C-17 aircrew and flight data. Accessing these data has been one of the greatest challenges, as old datasets were tossed out or housed in legacy systems that were hard to access and difficult to harmonize so that the model could pull from it all. “Once the data is connected, it’s then challenging to enumerate all of the constraints a scheduler considers,” says Matthew Koch, a graduate student in the MIT Operations Research Center.
For example, it’s straightforward to program the model around explicit constraints, such as the restrictions on how many hours a pilot can fly a day. Coding for implicit constraints is harder, or even impossible, and relies on the insight that an airman brings to the desk, such as knowing that two pilots’ personalities don’t mesh or that the strengths of one pilot will complement another’s weaknesses to build the safest flight.
That’s where the research team’s relationship with the C-17 pilots has been essential. “There have been so many user interviews,” Carter says. In those interviews, the pilots and research team discuss the nuances of different scheduling outputs—what they liked and disliked, and what they would change about certain decisions that the algorithm made. “Every step of the way, it’s been a very integrated relationship and allows us to improve our algorithm,” she says.
By design, the technology is an assistant. It’s still up to the human to accept the schedule. This approach, the team hopes, will make the system trusted and accepted by users, some of whom have spent years building their own approach to the problem. “We’re figuring out what buttons or charts we can add to the interface so that our algorithms aren’t black boxes. We want to keep the scheduler in the loop,” says Snyder.
Showing fairness and equity in their algorithms is also important. “We want to enable a level of explainability of why someone was scheduled over someone else,” Koch adds.
That goal is still aspirational. One technique to both improve the algorithm and to provide equity is to have the system present multiple schedules from which an airman can choose. Understanding why a user chooses one over the other allows the researchers to tweak the model further.
Today, the team is continuing to integrate their plugin with Puckboard and explore how to measure its success. “It’s hard to say that there is one optimal solution; there could be several different but very good schedules. It’s a bit of a trial-and-error process with users,” Koch says.
But, summing up the tool’s impact, McAlpin says, “It’s taking rocks out of rucksacks.”
The technology is particularly helpful under the realities of schedule disruptions. As McAlpin mentioned, an unexpected change can create a frustrating snowball effect, scrapping a two-week schedule that may have taken days to build. The algorithm easily accounts for sudden changes, and it can plan up to six months ahead. Changes are still inevitable, but the system allows airmen to gain more predictability around their schedules.
The team is considering other applications of their research. Puckboard is used widely across the Air Force for other scheduling needs, though each optimization problem is unique. “It’s a whole different set of efficiencies and a new set of problems, but that’s the exciting thing with these. It’s a nice thing for a researcher. We want to solve real problems,” Balakrishnan says.
In May, Koch defended his thesis on this project to complete his master’s degree. Sharing the sentiments of his colleagues, Koch says that the seamless collaboration between all three partner organizations in the DAF–MIT AI Accelerator program was invaluable. He himself personifies all three institutes, as an MIT student, a Lincoln Laboratory Military Fellow, and a lieutenant in the Air Force.
This article was written by Kylie Foy and originally appeared on MIT News on July 8, 2021. Image is courtesy of the researchers.