Imagine a robot that can pick up a pile of laundry from the back of a cluttered closet, deliver it to the washing machine, start the cycle, and then run to the kitchen to start preparing dinner.
This might have only been a domestic dream half a century ago, when the fields of robotics and artificial intelligence first captured the public imagination. However, it quickly became clear that even “simple” human actions are extremely complex to reproduce in robots. Now, computer scientists at MIT are solving this problem using a hierarchical, progressive algorithm that can significantly reduce the computational costs associated with performing complicated operations.
Leslie Kaelbling, professor of computer science and engineering at Panasonic, and Tomás Lozano-Pérez, professor of teaching excellence in the School of Engineering and co-director of the Robotics Center at MIT, present their approach in a paper titled “Hierarchical task and movement planning in the present” which they presented at the IEEE Robotics and Automation Conference earlier this month in Shanghai.
Traditionally, programs that enable robots to operate autonomously are divided into two types: task planning and geometric motion planning. The task planner may decide that it needs to go through the living room, but will not be able to find a path around furniture and other obstacles. The geometric planner can figure out how to get to the phone, but he can’t actually decide whether to make the phone call.
Of course, any robot that will be useful in the home must have a way to integrate these two types of planning. Kaelbling and Lozano-Pérez believe the key is to break down a computationally intensive larger goal into smaller steps, then make a detailed plan for just the first few, leaving the exact mechanics of the next steps for later. “We introduce hierarchy and aggressively break things down into manageable pieces,” says Lozano-Pérez. While the idea of hierarchy is not modern, researchers operate incremental division to create a timeline for their “in the present” approach, in which robots follow the age-old wisdom “step by step.”
The result is robots that are able to respond to environments that change over time under the influence of external factors as well as their own actions. These robots “perform execution interwoven with planning,” Kaelbling says.
The trick is figuring out which decisions need to be made ahead of time and which can – and should – be put off until later.
Sometimes procrastination is a good thing
Kaelbling compares this approach to the intuitive strategies that people operate for complicated actions. He uses a flight from Boston to San Francisco as an example: You’ll need a detailed plan to get to Logan Airport on time, and maybe you have an idea of how you’ll check in and board the plane. But once you arrive in San Francisco, you don’t bother planning a route through the terminal because you likely have no prior knowledge of what the terminal looks like, and even if you did, the location of obstacles such as people or luggage will surely have changed in the meantime. Therefore, it is better – and even necessary – to wait for more information.
Why shouldn’t robots operate the same strategy? Until now, most robotics researchers have focused on constructing complete plans in which each step from start to finish is described in detail before implementation begins. This is a way to maximize optimality – achieving a goal in the fewest number of moves – and ensure that the plan is actually achievable before it begins.
MIT computer scientists Leslie Kaelbling and Tomás Lozano-Pérez operate the Willow Garage PR2 robot to demonstrate their modern approach to integrating task planning and motion in robots
However, the researchers say that while this approach may work well in theory and simulation, when it comes time to run the program on the robot, the computational burden and real-world variability make it impractical to consider the details of each step from the beginning. -To go. “To get some feasibility, you have to introduce an approximation. You have to say, ‘No matter what happens, I can handle it,'” Lozano-Pérez says.
Their approach includes not only task planning, but also geometric planning: think of the computational costs associated with creating a precise map of every object in a cluttered kitchen. In Kaelbling and Lozano-Pérez’s “in the present” approach, the robot can construct a rough map of the area from which it will begin operating – for example, a countertop as a place to assemble ingredients. Later in the plan – if it turns out that the robot will need a detailed map of the middle shelf of the refrigerator to be able to, for example, reach a jar of pickled cucumbers – it will refine its model if necessary, using valuable computing power to model only those areas that are relevant for a given tasks.
Finding the “sweet spot”
Kaelbling and Lozano-Pérez’s method differs from the traditional end-to-end approach in that it may introduce suboptimal behavior. For example, a robot may pick up object “A” to move it to location “L”, only to reach L and realize that another object “B” is already there. The robot will then have to drop A and move B before it can grab A again and place it in L. Perhaps if the robot was able to “think ahead” far enough to check that L is unobstructed before picking up A, several additional movements could have been avoided.
But in the end, the robot still does its job. Scientists believe that it is worth sacrificing a certain degree of optimal behavior in order to be able to break down an extremely complex problem into manageable steps. “Computer science is all about trade-offs,” says Kaelbling. “We are trying to find some kind of ‘sweet spot’… where we trade efficiency of activities in the world for computational efficiency.”
Citing the field’s time-honored emphasis on optimal behavior, Lozano-Pérez adds: “We very consciously say, ‘No, if you insist on optimality, it will never be practical for real machines.'”
Stephen LaValle, a computer science professor at the University of Illinois at Urbana-Champaign who was not involved with the project, says the approach is attractive. “In robotics, we often tend to be very analytical and engineering-oriented — we want to determine every detail in advance and make sure everything will work out and be accounted for,” he says. “[The researchers] take a more confident approach so that we can figure out some details later in the process,” and in doing so, take advantage of the “computational load efficiency benefits.”
Looking to the future, researchers plan to build in learning algorithms that will support robots better assess which steps can be deferred and which should be addressed earlier in the process. To demonstrate this, Kaelbling returns to the travel example: “If you’re going to rent a car in San Francisco, you may need to plan ahead,” he says, because putting it off could be a problem in the future – for example, if you arrive and find that the agencies ran out of cars to rent.
While robotic “domestic helpers” are an obvious — and useful — application of this type of algorithm, the researchers say their approach could work in many situations, including supply depots, military operations and surveillance activities.
“So it’s not just about hiring a robot to do things in the kitchen,” says Kaelbling. “We like to think of this as an example, though, because anyone would be able to appreciate it.”