Pathfinding Prof

While visiting his hometown of Aspen, Colo., early last year, Michael Otte, an assistant professor of aerospace engineering, decided to hike up the slopes of the iconic ski area. At the top, he discovered his old high school running and skiing buddy, Rickey Gates, who’d independently had the same idea.

They hadn’t seen each other in over a year, and Gates, now a professional endurance runner, filled Otte in on his 2017 project to run across the United States, hitting the Appalachian Trail and other famous strands of dirt.

For his part, Gates knew that Otte worked in academia, possibly something to do with robots and math. “I knew he was an extremely smart guy and had his Ph.D., but I didn’t know exactly what he did,” Gates said.

Gates shared with Otte his latest vision for an epic run: He would pound the pavement down all 1,100 miles of streets in his current home of San Francisco. As with his cross-country journey, he would write about and photograph both the physical and human terrain he encountered—a mashup of athletics and sociology.

To Otte, it sounded more like a math problem. He realized the San Francisco project was closely related to one of his major areas of research, focused on giving autonomous robots the ability to determine optimal paths through the world.

“He asked me, ‘Do you know anything about finding efficient routes through streets?’” Otte said. “And I said, yeah, that’s exactly what I do.”

Otte’s immediate fascination with the project was a clue to how challenging it is to create efficient paths through complex spaces and networks. Otte told the runner it was related to an important problem in computer science and robotics known as the “Chinese postman problem,” created by a Chinese mathematician seeking to determine a perfect route for a letter carrier.

Otte offered to create a computerized algorithm to help Gates maximize his efficiency as he worked through his adopted city’s neighborhoods one by one. Gates began the run Nov. 1 and completed it on Dec. 17, averaging about 30 miles a day.

Yet Gates used the computerized route exactly as laid out on only two of the 45 days of running. The rest of the time he worked it out on a map by hand. One reason, he said, was the quality and currency of the street data. “If the map is telling you to go down this street and a construction worker is telling you to turn around, you have to find a different way,” he said.

Beyond that, a course that makes sense to a computer because it’s efficient in terms of mileage isn’t always the most enjoyable route for a human, said Gates, who plans to write a book about the run. (He’s currently at work on one about his cross-country experience.)

But that’s fine, Otte said; He was glad to collaborate with Gates on this problem, which pushed him in some new directions, and an academic paper describing the results is in the works.

“Having Rickey follow the algorithm's routes exactly was kind of a ‘reach’ goal," Otte said. "But our mutual obsession with the route tour problem lead to a number of cool insights that will hopefully be useful in a variety of research domains.”