11:08:00 / Endy Uzo / computers,
BYU computer science graduate student Daqing Yi has developed an algorithm that could lead to robots working on SWAT teams.
Yi, along with professors Michael Goodrich and Kevin Seppi, recently published a paper on multi-objective motion planning in the Proceedings of the Twenty-Fourth International Join Conference on Artificial Intelligence.
“The fundamental problem we’re trying to solve is how to get humans and robots to be on the same team,” Goodrich said. “Think of it like a SWAT team. They’re trying to surround an area of interest.”
In the paper, Yi, Goodrich, and Seppi present an algorithm that allows robots to interpret human directions and find the best way to obey them.
The algorithm is called MORRF, or “Multi-Objective Rapidly exploring Random Forest.” The probabilistic algorithm randomly simulates paths, allowing it to find better and better routes as it explores.
For example, if the human gives the direction to move quickly and secretly, the robot can look at the quickest and most secluded routes and use the algorithm to find the route that best meets both criteria. The longer the algorithm runs, the better the path the robot finds.
“The algorithm itself is really, really clever,” Goodrich said. “If you let the thing run long enough, you’re guaranteed to find the very, very best [solution].”
The BYU researchers have done simulation testing on computers, but Yi also tests out his algorithm with a small physical robot called a TurtleBot.
“It turns out that the TurtleBot can follow any of the paths that are chosen,” Goodrich said.
The next step, said Goodrich, is to build a user interface so a person can input directions without knowing all the computer science behind the program.
Another BYU student is working on building this interface, and it will take the form of a painter’s palette, allowing users to choose color representations of direction words. For example, selecting yellow might tell the robot to move slowly or choosing purple could indicate that the robot should travel quietly.
Goodrich and Seppi have mentored Yi during his research, but Yi has been the driving force behind MORRF.
“It was a student-driven paper,” Goodrich said. “It was his ideas.”
Yi originally reached out to Goodrich from China about earning a doctoral degree at BYU. Yi said his interest in coming stemmed from friends who have graduated from BYU and family friends who live in Salt Lake City.
“I thought it would be nice to stay close to someone,” Yi said. “It was kind of like a family here.”
Yi earned a degree in electrical computer engineering in China then worked for several years at a software company. After learning more about Goodrich’s research, his interest shifted from engineering to computer science.
“Dr. Goodrich is well known in the human-robot interaction field,” Yi said. “I read his publications and was very interested.”
After emails were exchanged and Yi had prepared to come to the United States, he was able to move to Provo and start his research. As he works, he takes proposals to Goodrich and Seppi for advice.
“Whenever I have an idea, I go to talk with them to hear their suggestions,” Yi said. “They usually give me very helpful feedback ... and that helps my research moving forward.”
Goodrich said Yi has jumped into life at BYU, becoming involved in the local culture and contributing to the Department of Computer Science.
“It’s really a tribute to his character and his work ethic,” said Goodrich. “When I have other students that come into the lab, he’s nurturing them.”
Yi has studied hard and made valuable contributions in his research area, as evidenced by the MORRF algorithm.
“He’s exactly the kind of student I want: bright, hardworking, good,” Goodrich said.
Because of Yi’s hard work, humans may soon work in tandem with robot teammates