Better marching through algorithms

Last semester, Tina Chow, professor of civil and environmental engineering (CEE), was looking for a problem that her 400 students could solve as a final project for E7, an introductory computer programming class for engineering undergraduates.

In years past, many E7 student projects focused on writing code for projects such as robot computer games. But Chow wanted to try something different. When not teaching, she uses numerical tools to study the flow mechanics of the lower portion of the atmosphere, with a goal of improving the computer code that supports weather forecasting and research.

So at the beginning of the semester, Chow started looking for project alternatives. “I wanted to find a project with a real-world application.”

Marching band choreography

One day, Chow happened to have a hallway conversation with one of her CEE colleagues, assistant professor Scott Moura (B.S.’06 ME), about her search for a good project. Moura had just been contacted by Kevin Durand, a student manager from the University of California Marching Band.

The band got in touch with Moura because he is a former member, and they needed his help. The student band managers were looking for software to help choreograph the moves of the massive ensemble. They had tried to write their own computer programs, but finding a good algorithm was an elusive problem.

So, even in the age of automation, algorithms and artificial intelligence, the Cal Band was crafting the marching transitions for their field choreography by hand. The problem is that it was taking hours to map out each of the band’s transitions — and every performance contained multiple transitions.

Being in the Cal Band is serious business; they most recently took the field in the national spotlight during Super Bowl 50 at Levi’s Stadium in Santa Clara, and this summer they toured and performed in Asia. Also — and this is the biggest wrinkle in terms of managing movements with computation — unlike many other college bands, Berkeley’s band marches in precise lines, not scattershot motions.

That’s where Chow and her class took up the problem: How do you write computer code to help guide dozens of bodies traversing in sync across a football field, avoid crashes and still pull off precision movements? And deliver a solution in the matter of a few weeks?

Chow brainstormed with two of the course’s graduate student instructors, Lucas Bastien and Brad Harken, both CEE graduate students, about how best to define the marching band’s problem and then develop a framework to build a solution around. “We worried it was going to be too hard,” Chow says. “But the band did have a real problem to solve.”

On the Wednesday before spring break, with brass-a-blaring, the band marched into a large lecture room in Dwinelle Hall, where E7 held its classes.

“We encouraged the students to brainstorm, to watch videos of the band, and we asked them why a human can plan the transitions, and why a computer couldn’t,” Chow says.  “We didn’t know what the solution would be when we assigned the project.”

The 400 students organized into small teams and got to work. One solution that a few teams pursued was the Hungarian algorithm, which was originally designed in the 1950s to optimize workforce decisions. Other teams tried other assignment or task-oriented algorithms.

“The hard part,” Chow says, “is finding a solution where they don’t collide, and then if there are collisions, then finding a new path or a new target. That’s a lot easier to do with [a band of] four people than it is to do with 180 people.”

“The elegance was in how they systematically went through the transitions and eliminated collisions. They kept fixing the movements until there were zero collisions.”

Out of 139 student groups hacking away at the problem, eight groups developed a computer program to solve most band transition issues in a matter of minutes. Of the eight, three groups developed solutions that solved all of the transitions in the assignment.

One group developed an algorithm that could solve the assignment transitions and then some.

Chow asked the band for formations that were not in the original assignment, and the algorithm developed transitions for those too.

Now the band has a new tool to use. While there is no expectation of a quid pro quo, Chow does say, “Ultimately, it would be super cool if the band performed an E7 formation.”