|Head: Howie Choset
Carnegie Mellon University
Professor Choset’s education and research interests straddle the border between computational theory and mechatronic engineering implementation: rigorous mathematical results enable engineering advancements while the practical aspects of implementation drive theoretical derivation. Professor Choset’s research program centers on two foci: highly articulated system and coverage tasks. One such highly articulated system is a snake robot which can exploit its many internal degrees of freedom to thread through tightly packed volumes accessing locations that people and conventional machinery otherwise cannot. The two great challenges facing snake robot research is design and path planning. Since we are interested in applications such as urban search and rescue and inspection of engines, our snake robots must maneuver in three-dimensions and still posses a small cross-sectional diameter. Our current designs maximize mechanical strength per cross-section diameter by allowing the point of power transmission to occur at the periphery of the device. Ultimately, Professor Choset’s long-term goal is to develop highly articulate snake-like robots for minimally invasive surgery; the idea here is that the snake robot can reach deeper into the body without a need for additional or large incisions. Currently, his group is developing a device for cardiac surgery.
Once the snake robot is built, it still requires control. Simple engineering hacks alone are not sufficient to coordinate the internal degrees of freedom to allow for purposeful motion. Essentially, the robot must plan in a multi-dimensional, one for each degree-of-freedom, space. Our approach uses a retract-like structure of the space, which reduces planning from a multi-dimensional search problem to a one-dimensional search. In 1997, Professor Choset received the NSF Career award to develop this retract-like structure. However, the retract structure is not enough; each path generated by the retract must be optimized so that the snake robot can more easily follow it. Naturally, with all optimization problems, we must contend with local minima. Here, we take recourse to homotopy theory where were the retract-like structure serves as a topological map that seeds a set of candidate searches of the robot’s free space, one of which leads to the global optimum. Here, we are exploiting the natural topology encoded in the free space to divide into regions each having simple structure and optimizing within each simple space a cost function. This approach is general: the cost function can be anything: path length, safety, energy, etc. For snake robots, we have defined a “snake robot” cost function. Currently, we are developing new techniques for the snake robot to crawl and climb in three-dimensions.
Our topological mapping routines have the added benefit in that they automatically induce well-defined sensor-based control laws that can direct a robot to explore an unknown space. However, one of the critical challenges in exploring unknown spaces is localization. Nominally, a robot has encoders on its wheels that count the number of times the wheels rotate and after integrating this information, the robot determines its location. Due to slippage of the robot’s wheels on the floor, the robot accrues localization error. Initially, we have developed a topological approach to simultaneous mapping and localization (SLAM). This approach scales well into large spaces but does not provide a high resolution map of the area. Conventional feature-based approaches, mainly based on Kalman filtering and Bayesian techniques, provide a high resolution map, but do not scale. Recently, we developed a hierarchical SLAM technique where we use the topology to divide the free space into regions where high resolution maps can be created. This approach scales well because one giant high resolution map is never created and yet a large space in represented by a collection of maps tied together by a topological map.
This symbiosis of applied math and engineering has already had impact on a vital area, the robotic search for mines. Professor Choset’s group has developed provable techniques for coverage path planning, a method that determines a path for a robot to follow such that the robot passes over every point in the environment. The mathematical guarantee is critical in mine-sweeping where missing one mine makes the mission a failure. In 1999, the Office of Naval Research awarded professor Choset its Young Investigator Program award to further work in de-mining, both on land and in the surf zone. The approach we take to coverage uses a cellular decomposition, a representation where the environment is divided into cells and a graph is formed encoding the adjacent relationships (topology) among the cells. Since we use critical points of Morse functions to define the cell boundaries, coverage in each cell is “simple,” and thus complete coverage of a target region is achieved by visiting each cell in the decomposition, i.e., finding a walk through the adjacency graph.
In many situations time may not permit covering a target environment completely, as may be the case in robotic de-mining. However, if the planner has access to a probabilistic map of mine locations, it can guide opportunistically the robot. For mine fields that have been laid out in a pattern, we developed a Bayesian-based method of efficiently decoding the parameters that describe the minefield. Once these are known, the robot can cover a small fraction of the target region and locate most of the mines. This work is done in collaboration with Mark Schervish in Statistics here at CMU.
In collaboration with the Johnson Space Center, the coverage work has been lifted into three-dimensions to investigate the inspection of structures in space with a free-flying robot called AERCam. Also, in collaboration with Dr. Rizzi at Carnegie Mellon, Professor Choset applied similar coverage technology to the application of auto-body painting with the Ford Motor Company to expedite the paint operation while minimizing hazardous waste. The paint work is also coverage in three-dimensions, but it must respect the dynamics of the paint applicator. Already, we have demonstrated utility of this work are car body parts painted at Ford. The next step in this research thrust is to apply coverage to develop software tools for semi-automated milling for both rapid prototyping and surgical bone shaping with a minimally invasive device.
In the above research endeavors, Professor Choset’s group has brought the realities and uncertainties of mechanical systems into harmony with the precision of applied math and computer science. This philosophy of using construction and implementation to reinforce theory permeates Professor Choset’s courses. In Professor Choset’s undergraduate robotics course, students use LEGO robotics labs, developed by Professor Choset and his students, to reinforce the rigorous and theoretical materials presented in class (http://generalrobotics.org). Every two weeks, lecture material covers the underlying mathematics and algorithms and via construction of a programmable three-dimensional artifact, the lab experiences seriously motivate students to synthesize lessons, critically explore beyond them, and then think creatively with meta-lessons. Professor Choset termed this style of education as directed constructionism because it strikes a balance between conventional on-way lectures and modern constructionist approaches.