Research helps people, lunar rovers, get there on time

Graduate student Pranay Thangeda relies on the bus system in Champaign-Urbana to get to class and other meetings. He wanted to understand why,

despite arriving at the bus stop well ahead of the schedule, he was sometimes late. He developed a tool that considers transportation variables weighed against how great a margin of error bus riders are willing to accept. The basic concept can also apply to getting a lunar rover where it needs to be, and with a high degree of reliability.

“I was following the real-time bus schedule but still ended up being late to my destination almost half of the time and being early the other half. I wanted to know what was happening,” said Thangeda, an aerospace engineering student who studies under CSL faculty member Melkior Ornik.

Thangeda realized that most navigation apps only cared about the expected travel time: they only announce how long the trip is expected to take. If the expected travel time is 20 minutes but half of the time it takes them 10 minutes and half of the time takes 30 minutes, that is often unacceptable—the rider would be late half of the time.

“We started the research with Pranay’s experience: sometimes bus riders care about reliability and not just the expected fastest route. They want to have a 90 percent or 95 percent certainty that they’ll get there in time for their meeting,” Ornik, assistant professor in aerospace engineering, said.

When Thangeda and Ornik began building the model, they wanted real time data and a lot of it.

“We could have collected our own data, but I noticed that MTD’s website had a good web application programming interface with open access, so we reached out to their operations manager,” Thangeda said. “We met with Jay Rank at MTD’s office, talked over the data and he got it for us in less than a week. He and Evan Alvarez were both very gracious and accommodating. We used the data to train the model to determine the underlying distribution of travel times on different road segments and their correlation.”

Thangeda said there were a lot of variables to consider in the data.

“Each factor has its own unique implications on the distribution and uncertainties,” Thangeda said. “Variations in pedestrian traffic, changes to road conditions due to the weather, bus breakdowns, and other conditions. What we focused on is how these factors are distributed by using the overall distribution of historical data and live data from all the bus apps available. That enhanced the model and reduces the uncertainty making it more feasible to predict what's going to happen next.”

This first step in the research resulted in a proof-of-concept implementation.

“We showed the model can calculate the tradeoff between reliability and expectation between any starting bus stop and destination,” Thangeda said. “The next step would be to develop an app so users can get the optimum route from any starting point to any ending point. Developing an app will depend upon resources and the time to create it.”

Ornik said they’d like to develop an app that provides complimentary functionality to currently available apps.

“Google Maps has a public transit planner. You enter your starting and ending points and it tells you the route it wants you to take. But that route might be expected to be fast but have a low reliability. We want users to be able to set their starting and ending point, the exact time they need to be there, and a tolerance such as I’m okay with being late 5 percent of the time,” Ornik said.

Given that many of the current apps are free, Ornik added that there’s no incentive to develop a new app. “The hope is however that this work can steer us toward an academic or industry transport partnership,” he said.

Thangeda and Ornik both described some surprises in the research.

“There were a few surprises in the data,” Thangeda said. “We have a static model of the entire city that’s updated every three months. There were a few errors that had to be fixed. There was also some noise possibly because of the way the sensors on the buses publish the data. Sometimes the stops were recorded in an uneven order, so we had to spend a lot of time on pre-processing the data.”

Ornik said he was surprised at a specific point-to-point solution the tool recommended for a trip from downtown Urbana to the Illinois Terminal in Champaign where connections can be made to Amtrak and other bus services.

“Champaign-Urbana is a fairly tame environment in terms of traffic—there isn’t a rush hour or even the high pedestrian numbers you have in cities like Chicago or New York City,” Ornik said. “And yet, if you want to be more certain  about your arrival time, it is better to take the Orange line that takes a longer route on University Avenue and avoids campus than to take the Green line that goes through campus. That route becomes questionable because of the large fluctuation of students on campus, which increases the variance of travel times. Consequently, it makes sense to take the Orange. I never thought of that. It was very satisfying to work with these data and demonstrate specific practical features like this one in Champaign-Urbana.”

Ornik said the study only looked at peak times when school is in session. The Green line may be a good choice during the summer months when the student population in C-U is lower.

The same issues addressed in the study can be said of car travel.

“We are looking for ways to translate this work further away from public transit,” Ornik said. “The big difference with cars is that there are no fixed routes. In a car, if you realize that the traffic is moving slowly you can switch to a different road. In a bus, there’s not much you can do.”

This work was partially funded by a 2018 NASA Early Stage Innovation Award, which is not directly related to public transit but has to do with optimal planning.

“The original case study was on a lunar rover which has the same principles,” Ornik said. “The rover has an origin and a destination. We look at the reliability and expectation tradeoffs between the expected amount of energy or the expected amount of time that the rover will take to reach its destination based on the terrain and what we know of the agent’s energy consumption. There’s also the question of reliability. Can I ensure, not just expect, that the rover will reach its destination without running out of energy. I want hard guarantees here.”

The study, “PROTRIP: Probabilistic Risk-Aware Optimal Transit Planner,” was presented this week by Pranay Thangeda and Melkior Ornik as part of the 23rd IEEE International Conference on Intelligent Transportation Systems.