When a robot is moving one of its limbs through free space, its behavior is well-described by a few simple equations. But as soon as it strikes something solid — when a walking robot’s foot hits the ground, or a grasping robot’s hand touches an object — those equations break down. Roboticists typically use ad hoc control strategies to negotiate collisions and then revert to their rigorous mathematical models when the robot begins to move again.
Researchers at MIT’s Computer Science and Artificial Intelligence Laboratory are hoping to change that, with a new mathematical framework that unifies the analysis of both collisions and movement through free space. The work could lead to more efficient controllers for a wide range of robotic tasks, but it could also help guarantee the stability of control algorithms developed through trial and error — or of untried, but promising, new algorithms.
In a pair of recent papers, the researchers demonstrate both applications. At last year’s International Workshop on the Algorithmic Foundations of Robotics, they showed how their technique can improve trajectory planning in complex robots like the experimental Fast Runner, an ostrich-like bipedal robot being built at the Florida Institute for Human and Machine Cognition.
And in a paper that has been short-listed for the best-paper award at this year’s Hybrid Systems: Computation and Control conference in April, they use their framework to establish stability conditions for some simple mechanical systems undergoing collisions.
According to associate professor of computer science and engineering Russ Tedrake, whose group did the new research, Fast Runner offers a good illustration of the problems posed by collision. Ordinarily, Tedrake says, a roboticist trying to develop a controller for a bipedal robot would assume that the robot’s foot makes contact with the ground in some prescribed way: say, the heel strikes first; then the forefoot strikes; then the heel lifts.
“That doesn’t work for Fast Runner, because there’s a compliant foot that could hit at any number of points, there’s joint limits in the leg, there’s all kinds of complexity,” Tedrake says. “If you look at all the possible contact configurations the robot could be in, there’s 4 million of them. And you can’t possibly analyze them all independently.”
The mysterious table
Even that combinatorial explosion, however, doesn’t do justice to the complexity of the problem. “Not only do you have this immense number of potential contacts and trajectories, but you also have things like non-uniqueness of solutions,” says Michael Posa, a graduate student in Tedrake’s group and lead author on both new papers. “Given the laws that we would normally write down that describe the evolution of the system, there may be multiple trajectories that are going to satisfy that because of the oddities of friction laws.”
To illustrate this idea, Tedrake uses the analogy of a four-legged table resting on the ground. “If you give the table a push, we don’t have any models that will predict what that table’s going to do,” Tedrake says.
In Newtonian physics, Tedrake explains, the table would be modeled as an aggregate mass. But that model leaves open an infinite number of possibilities for the distribution of mass across the table’s legs. Since the effects of friction depend on the specifics of the distribution, the classical model underdetermines the behavior of the table when shoved.
In order to prove the stability of a control system for a robot that’s colliding with the world, then, it’s necessary to evaluate not only every possible configuration of the point of the contact, but also every possible solution of the resulting equations. That’s precisely what Posa and Tedrake — together with Mark Tobenkin, another grad student in Tedrake’s group, and Cecilia Cantu, an undergraduate major in mechanical engineering — have found a way to do.
Expression compression
The key to their approach is to describe opposed possibilities for the state of a robotic system using simple algebraic expressions. For instance, as the foot of a bipedal robot approaches the ground, either the force exerted by the ground — call it F — or the distance to the ground — call it d — is equal to zero. So the equation Fd = 0 holds whether the robot’s foot is moving through free space or touching the ground. Just a few such equations give the researchers enough mathematical purchase on the problem of collision that they can draw boundaries around the whole space of solutions.
The result is not a precise description of how a robot will behave in any given instance, but it is enough to offer guarantees of stability. Again, Tedrake explains by invoking the table analogy. “Given all the things I know about the frictional forces on the legs, I can’t tell you where the table’s going to go,” Tedrake says. “But I can tell you that it won’t hit the wall.”
“The hardest thing about robots, especially if you want to get them to do something very dynamic, is when these contact points with the world change,” says Aaron Ames, an assistant professor of mechanical engineering at Texas A&M University and head of the A&M Bipedal Experimental Robotics Lab. “If you’re trying to assess some stability notion with all those things changing, it’s this huge complexity explosion that most people just haven’t wanted to deal with. It’s too much to wrap your head around, so very few people have been brave enough to attack it.”
Ames acknowledges that, so far, the MIT researchers have applied their analytic techniques only to simple systems. But “the way their stuff is framed is in a general context that would be applicable to more complex systems,” Ames says. “The pieces are there. At least the starting point is there. And it’s a very good one.”
Researchers at MIT’s Computer Science and Artificial Intelligence Laboratory are hoping to change that, with a new mathematical framework that unifies the analysis of both collisions and movement through free space. The work could lead to more efficient controllers for a wide range of robotic tasks, but it could also help guarantee the stability of control algorithms developed through trial and error — or of untried, but promising, new algorithms.
In a pair of recent papers, the researchers demonstrate both applications. At last year’s International Workshop on the Algorithmic Foundations of Robotics, they showed how their technique can improve trajectory planning in complex robots like the experimental Fast Runner, an ostrich-like bipedal robot being built at the Florida Institute for Human and Machine Cognition.
And in a paper that has been short-listed for the best-paper award at this year’s Hybrid Systems: Computation and Control conference in April, they use their framework to establish stability conditions for some simple mechanical systems undergoing collisions.
According to associate professor of computer science and engineering Russ Tedrake, whose group did the new research, Fast Runner offers a good illustration of the problems posed by collision. Ordinarily, Tedrake says, a roboticist trying to develop a controller for a bipedal robot would assume that the robot’s foot makes contact with the ground in some prescribed way: say, the heel strikes first; then the forefoot strikes; then the heel lifts.
“That doesn’t work for Fast Runner, because there’s a compliant foot that could hit at any number of points, there’s joint limits in the leg, there’s all kinds of complexity,” Tedrake says. “If you look at all the possible contact configurations the robot could be in, there’s 4 million of them. And you can’t possibly analyze them all independently.”
The mysterious table
Even that combinatorial explosion, however, doesn’t do justice to the complexity of the problem. “Not only do you have this immense number of potential contacts and trajectories, but you also have things like non-uniqueness of solutions,” says Michael Posa, a graduate student in Tedrake’s group and lead author on both new papers. “Given the laws that we would normally write down that describe the evolution of the system, there may be multiple trajectories that are going to satisfy that because of the oddities of friction laws.”
To illustrate this idea, Tedrake uses the analogy of a four-legged table resting on the ground. “If you give the table a push, we don’t have any models that will predict what that table’s going to do,” Tedrake says.
In Newtonian physics, Tedrake explains, the table would be modeled as an aggregate mass. But that model leaves open an infinite number of possibilities for the distribution of mass across the table’s legs. Since the effects of friction depend on the specifics of the distribution, the classical model underdetermines the behavior of the table when shoved.
In order to prove the stability of a control system for a robot that’s colliding with the world, then, it’s necessary to evaluate not only every possible configuration of the point of the contact, but also every possible solution of the resulting equations. That’s precisely what Posa and Tedrake — together with Mark Tobenkin, another grad student in Tedrake’s group, and Cecilia Cantu, an undergraduate major in mechanical engineering — have found a way to do.
Expression compression
The key to their approach is to describe opposed possibilities for the state of a robotic system using simple algebraic expressions. For instance, as the foot of a bipedal robot approaches the ground, either the force exerted by the ground — call it F — or the distance to the ground — call it d — is equal to zero. So the equation Fd = 0 holds whether the robot’s foot is moving through free space or touching the ground. Just a few such equations give the researchers enough mathematical purchase on the problem of collision that they can draw boundaries around the whole space of solutions.
The result is not a precise description of how a robot will behave in any given instance, but it is enough to offer guarantees of stability. Again, Tedrake explains by invoking the table analogy. “Given all the things I know about the frictional forces on the legs, I can’t tell you where the table’s going to go,” Tedrake says. “But I can tell you that it won’t hit the wall.”
“The hardest thing about robots, especially if you want to get them to do something very dynamic, is when these contact points with the world change,” says Aaron Ames, an assistant professor of mechanical engineering at Texas A&M University and head of the A&M Bipedal Experimental Robotics Lab. “If you’re trying to assess some stability notion with all those things changing, it’s this huge complexity explosion that most people just haven’t wanted to deal with. It’s too much to wrap your head around, so very few people have been brave enough to attack it.”
Ames acknowledges that, so far, the MIT researchers have applied their analytic techniques only to simple systems. But “the way their stuff is framed is in a general context that would be applicable to more complex systems,” Ames says. “The pieces are there. At least the starting point is there. And it’s a very good one.”
