Collision-free Cal Band
Last spring, Tina Chow, professor of civil and environmental engineering, was looking for a real-world problem for her 400 students to solve as a final project for E7, an introductory computer programming class for engineering undergraduates.
She found out the University of California Marching Band needed help developing a computer code to program transitions for their field routines — the band’s search for a good algorithm kept coming up short, and crafting formations by hand takes hours. “We encouraged the students to brainstorm and watch videos of the band. We asked 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.”
Working in teams of twos and threes, several groups managed to develop efficient computational choreography. Some of the groups used the Hungarian algorithm, developed in the 1950s for economically assigning workers to tasks. “The elegance was in how they systematically went through the transitions and eliminated collisions,” Chow says of the student projects. “They kept fixing the movements until there were zero collisions.”
“We worried it was going to be too hard,” Chow says. “But the band did have a real problem to solve.” And the E7 students were able to solve it.