当前位置:首页 >> 电力/水利 >>

The International Journal of Robotics Research-1996-Krotkov-155-80


Eric Krotkov Reid Simmons
Robotics Institute Carnegie Mellon University Pittsburgh, Pennsylvania 15213

Perception, Planning,
and Control for Autonomous Walking With the Ambler Planetary Rover

Abstract
Producing a robotic system that can operate autonomously on other planets is a challenging task: The robot must be extremely self-reliant; it must be able to operate on a limited power budget; and it must be able to traverse a wide range of rugged terrain features. This article describes an integrated software system that combines perception, planning, real-time control, and task-level control to navigate autonomously the Ambler, a six-legged rover. The overall approach to walking is highly deliberative: Where actions are goal-directed, steps are planned out in detail using explicit models of the terrain and the vehicle, and moves are checked for safety prior to execution. We believe that this approach is well-suited to meeting the challenges of reliability, efficiency, and terrainability faced by autonomous planetary rovers. The Ambler system has been extensively tested, both indoors and outdoors, and the results confirm our expectations regarding the degree of system capability and performance afforded by our approach.

decouple horizontal and vertical motions, leading to simplified planning and control. Further, the design increases mobility by allowing legs to be placed adjacent to steep
terrain features, such as sheer faces of rocks. The stacked arrangement of legs enables the Ambler to exhibit a unique circulating gait. To move forward, one rear leg circulates through the body cavity, moving ahead of the other two legs on its stack (see Fig. 10). This process repeats as the robot walks to its destination. The circulating gait reduces the number of footfalls needed to cover the same distance as a comparable follow-the-leader walker, increasing efficiency and reducing planning and

perception

1. Introduction
To operate in remote, natural environments, a mobile robot system needs to be highly reliable, capable, and efficient. These requirements extend to both the hardware and software aspects of the robotic system. This article presents results of our investigation of perception, planning, real-time and task-level control for the Ambler, a six-legged walking robot. The result is a robot system that can autonomously traverse rugged terrain for extended periods of time. The Ambler (Fig. L) is built for mobility and efficiency. A related article (Bares and Whittaker 1994) describes in detail the configuration and physical form of the robot. The Ambler’s novel features include stacked, orthogonal legs (as in Fig. 1) and the ability to walk with a circu-

needs. The Ambler is totally self-contained and equipped with on-board computing and power. Computation is provided by two 68020 boards for real-time control and one SPARC workstation each for planning and perception. Power is provided by a combination of batteries and a propane generator. Sensors on the Ambler include both relative and absolute encoders, inclinometers to measure tilt, six-axis force/torque sensors on the feet, a scanning laser rangefinder for mapping terrain, and a black-and-white camera to aid in position estimation. The robot communicates with an off-board graphical user interface via a radio Ethernet link.

1.1.

Objective

objective of this work is to enable robotic exof remote, natural areas. We consider exploration missions with two defining characteristics:
The chief

ploration
~

lating gait.

The

three-degree-of-freedom orthogonal legs
~

Remote area: By &dquo;remote&dquo; we mean conditions under which teleoperation is either not feasible (typically because of delay) or not economical (typically because of the high cost of ground support). Natural environment: The forces of nature produce irregular shapes and materials, causing natural

155
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

Fig. 1. The Ambler.
terrain to exhibit roughness over a wide range of scales (Burrough 1981 ). There are no prepared surfaces in nature. To make our objective more concrete, we choose the Mars as an instance of an area that is remote, natural, and unexplored. Others have detailed the expected benefits of observing geophysical, meteorological, and biological conditions on Mars and have assessed the risks and costs of sending human crews as highly dangerous and very expensive (Office of Technology Assessment 1991). Robotic exploration of Mars provides an alternative that eliminates risk to human lives and promises to substantially reduce mission cost. These objectives are also present in many environments on Earth. For example, the ideas discussed in this article may apply equally well to other remote areas such seabeds, volcanos, and subsurface mines. Further, creating a robot with the capability to explore Mars is a motivation, not an objective. As a consequence, the research does not require flight-qualified components for computing, data storage, or communications, nor does it require formulation for extremes of gravity, vacuum, or other conditions. There are three specific challenges addressed by the Ambler project that follow from the stated objectives: self-reliant control, limited power, and rugged terrain traversal. These challenges affect each part of the integrated walking system-perception, planning, real-time control, and task-level control-and, in Section 3, we describe how each of the systems faces the three challenges.
.

planet

Self-reliant control: The remoteness of the area to be explored affects the feasibility and cost of different control regimens, ranging from pure teleoperation (reliance on operator) to pure rover autonomy (reliance on self). Regimens from the teleoperation end of the spectrum are less feasible, because round-trip signal delays preclude the rover from responding quickly to hazardous conditions (e.g., sinking into quicksand), and less economical, because they require costly ground support. The challenge is self-reliant control that enables timely
rover

responses, requires little human interaction, and enables operation for extended periods and distances. The longer the duration and wider the coverage, the greater the likelihood of meaningful return from exploration missions.

156
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

~

Limited power: The remoteness of the area requires the rover to supply its own power, which in turn dictates power budgets that are meager by laboratory standards. Limited power places a premium on efficiency of operation and penalizes unproductive behavior such as bumping into obstacles (which transfers energy to the terrain) and wandering repeatedly in the same small subregion (which serves

1.

Autonomy: Our approach is

to develop planning algorithms to evaluate conservatively each Ambler motion, checking them several times for feasibility and stability. While executing the plan, if robot sensors indicate signs of trouble, then reactive be-

~

exploration purpose). Rugged terrain traversal: The surface of Mars viewed by the Viking landers is rugged, uneven, and rocky (Fig. 2). This terrain challenges most
no

mobile robot mechanisms (Bares and Whit1994). Even with a suitable form of locomotion, the terrain poses significant challenges to stability control, since the surface may shift, fracture, or deform. The irregular terrain also challenges established machine perception techniques, because it does not satisfy standard constraints on

existing
taker

haviors stabilize the robot. This combination of approaches enables the Ambler to operate for extended periods. 2. Explicit models: To facilitate the deliberation necessary to plan good moves, we need to model both the environment and the capabilities and limitations of the robot. In particular, the Ambler walking system explicitly models the terrain geometry, mechanism kinematics, vehicle stability margins, and sensor uncertainty. These models play critical roles in meeting the challenges described above.
~

shape (e.g., symmetry)
nor

or

surface

properties (e.g.,
~

does it admit controlled lighting smoothness), or fixtured objects, and it challenges planning techniques, since the irregularly shaped robot must move in three dimensions while avoiding terrain collisions

and self-contact.
We determined that a legged robot would best be able these challenges. In particular, walking has advantages over rolling in mobility and efficiency. Walkers have relatively high ground clearance, and they contact the terrain at only a few discrete points. This allows walkers to surmount higher obstacles and traverse more rugged terrains. Similarly, unlike rolling and crawling mechanisms, walkers are able to select favorable footholds, avoiding transferring energy to terrain by unsupportive contact. Finally, the use of legs isolates the walker’s body from the underlying terrain, enabling sensors and scientific equipment to travel along smooth and
to meet

~

Models of terrain geometry enable planners to select favorable footholds, thus meeting the challenge of rugged terrain traversal and capitalizing on the highmobility characteristics of walking robots. Models of terrain geometry permit planners to select leg and body motions minimizing terrain contact, thus meeting the challenge of limited power. Models of mechanism kinematics allow controllers to accurately execute the plans, thus addressing the challenges of rugged terrain traversal and limited
power.

~

Models of stability margins allow planners and controllers to ensure the safety of different motions, thus meeting the challenge of extended operation under self-reliant control.

predictable trajectories. The results of this project are primarily in the design of a capable legged robot (Bares and Whittaker 1994); its
the real-time and task levels; 3D percepunstructured terrain; and planning at the and gait, footfall, leg-recovery levels. All this provided the basis for autonomously operating the Ambler in fairly rough terrain. However, this project did not address issues of extreme long-term reliability, planetary exploration, or global navigation. We are currently in the midst of a successor project that addresses these important issues.
at

While the complexity of the models is high compared purely reactive approaches, the complexity produces significant benefits. In particular, using models to plan and analyze moves contributes to the rover’s safety and power efficiency, which are primary concerns for planeto

tary missions.
This article proceeds as follows: Related research is reviewed in the next section, and Section 3 presents the integrated walking system. Section 4 documents experimental walking results, and the article concludes with a summary, an evaluation, and a look toward the future.

control, both
tion for

rugged,

2. Related Research
Researchers have advanced a spectrum of mobile robot concepts suited for exploring remote, natural environments. In this section we review relevant mobile robots that have been built and operated. In general, the variety of related research in this area has (1) produced mechanisms with high mobility but without high autonomy, (2) researched autonomous units

1.2.

Approach
to

There are two distinguishing features to our approach enabling high-performance autonomous walking:

157
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

Fig.

2. Martian

surface.
I at MIT have argued that small rovers ( kg) are suitable for planetary exploration (Brooks and Flynn 1989) and lunar base construction (Brooks et al. 1990). They have developed the Attila family of small six-legged walkers and are striving to make the robots totally autonomous units using the subsumption architecture and &dquo;behavior languages&dquo; (Angle and Brooks 1990). Although the degree of autonomy inherent in their approach is high, the potential for efficiency ap-

but without mission capabilities, and (3) developed autonomous systems with mission capabilities but only in structured environments. To our knowledge, there are no robot systems other than the Ambler that combine high mobility, high autonomy, reliability, and mission capabilities for use in unstructured, remote, natural environments. Sustained effort by researchers at NASA’s Jet Propulsion Laboratory (JPL) has led to the development of a family of rovers that includes the Surveyor Lunar Rover Vehicle, Robby, Rocky, Go-For, and the Mars Pathfinder microrover. Using these wheeled mechanisms as testbeds, JPL researchers have developed control architectures, such as computer-aided remote driving (Wilcox and Gennery 1987), behavior control (Gat et al. 1994; Gat 1992), semi-autonomous navigation (SAN) (Wilcox et al. 1992), and mission-specific hybrids (Stone 1993), which share mission control between human operators and robots. Using these control architectures, various vehicles have successfully demonstrated navigation in desert settings. Still, the degree of autonomy is limited even with SAN, which requires more computation and look-ahead planning than the other control architectures. Researchers at Laboratoire d’Analyse et d’Architecture des Syst6mes (LAAS) have developed a complete system that provides for mission planning and supervision from a ground station and for on-board mission interpretation and execution (Chatila et al. 1993). They have demonstrated this system with a six-wheeled rover called ADAM in an experimental testbed called EDEN. The demonstration involved execution of a &dquo;GO-TO(Landmark)&dquo; task. Although the degree of autonomy is high, the system has yet to be tested in extreme terrain for long durations.

Researchers

to 2

pears to be low. For example, local behaviors may cause the rover to take suboptimal actions, causing the rover to transfer substantial energy to the terrain by repeatedly bumping into obstacles. Worse, unanticipated interactions between behaviors may cause the rover to take actions that are hazardous to its well-being. Researchers advocating behavior-based rovers point out that it is feasible to send many such rovers, and thus it is not important if some do not survive (Brooks and Flynn 1989). However, it is entirely possible that each rover will exhibit the same behavioral problems, causing all to fail. Other researchers have built and operated prototype
rovers, including the Quadra-Rhomb (Hiand Ootsukasa 1993), the Marsokhod (Kemurdjian et al. 1992), and the Walking Beam (Chun et al. 1989). To date, these research efforts have concentrated primarily on mechanical design and real-time control and have not yet addressed or achieved autonomous performance. Mobile roboticists have developed a number of integrated systems that exhibit (or potentially exhibit) relatively high degrees of autonomy. Examples of indoor robots with autonomous capabilities include Hilare (Chatila and Laumond 1985), the longest-running mobile robot project, and many others. Examples of

planetary
rose

158
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

outdoor robots with autonomous capabilities include the Autonomous Land Vehicle (Turk et al. 1988), the Navlab (Thorpe 1990), and VaMoRs (Dickmanns and Mysliwetz 1992). These robots typically operate in environments relatively rich in structure (e.g., well-defined hallway corridors, or roadways with lane markings) compared to planetary surfaces. Researchers have developed a variety of walking mechanisms with the high mobility required by planetary rovers. These walkers include the Adaptive Suspension Vehicle (Song and Waldron 1989), Titan I through Titan VI (Hirose 1984; Hirose et al. 1991), the Odex (Russell 1983), the Recus (Ishino et al. 1983), the Aquabot (Ishino et al. 1983), and hopping machines (Hodgins and Raibert 1991; Raibert 1986). Many of these efforts emphasize electro-mechanical design and performance. Thus, these robots tend to be either teleoperated or operate under supervisory control, so the degree of autonomy achieved is low.

to the image queue module requesting subimages that contain laser range data relevant to constructing the desired terrain map. The mapping module then combines the images to construct a terrain elevation map, and returns the map to the footfall planning module. The footfall planner uses a neural network to evaluate the terrain map, estimating the goodness of each foot-sized patch in terms of stability and traction. The gait planner then chooses the best footfall location within the specified

request

region.
After setting a leg move, the gait planner finds the maximum body move that follows along the arc, one that does not violate limits on leg motion, and keeps the Ambler’s center of gravity within the conservative support polygon (CSP) (Fig. 5). This guarantees that the Ambler won’t tip over even if any single leg fails. The gait planner then forwards the chosen leg move to the leg-recovery planner, which plans a fast trajectory that avoids terrain collisions. The chosen leg and body moves are then forwarded to the real-time controller module. Concurrently, if the end of the arc has not been reached, the gait planner qtarts planning the next pair of leg and

3.

Integrated Walking System

This section describes each of the modules illustrated in Figure 3: the perception modules, which acquire images and construct terrain elevation maps; the planning modules, which plan leg and body movements; the real-time module, which controls the robot and monitors its internal sensors; the task-control module, which coordinates components and monitors progress; and the graphical user interface, which enables paths to be entered.

body

moves.

3.1.

Example of Operation

To initiate
arcs

walking,

a

human operator

inputs

a

series of

(that is, arcs of a circle) via a graphical user interface (Fig. 4). The user indicates desired waypoints and the orientation to be achieved at each, and the user interface then computes a series of arcs to achieve those position and orientation constraints. Each arc is forwarded in turn to the gait planning module, which plans a series of leg and body moves. The gait planner first determines the leg that maximizes subsequent body motion. It finds a region of geometrically feasible footfalls based on the limits of the leg’s motion, the need to avoid colliding with the current leading leg, the desire to avoid placing the leg in the path of the body, and the need to maintain support in subsequent moves (Wettergreen et al. 1990). Next, the terrain within the footfall region is analyzed to estimate the goodness of the footfalls. The footfall planner sends a request to the perception subsystem for a terrain elevation map within the boundaries of the footfall region. The local terrain mapping module sends a

The real-time controller generates leg move trajectories that are linear in joint space, coordinating the leg joints so that all motions start and end simultaneously. The controller module checks the leg move for feasibility, refusing to perform the move if it would exceed kinematic or geometric limits. During execution, the controller monitors the force sensors in the feet and the inclinometers. If an unexpected terrain collision or tilt occurs, all motions are halted, the brakes are engaged, and an exception is raised to the task-level controller. Many of these exceptions are handled autonomously (see Section 3.4.2), and walking continues once the steps are replanned. In a similar manner, the real-time controller executes planned body moves. It computes, for each leg, the trajectory of horizontal joint motions that will simultaneously translate and rotate the body to achieve the commanded position. The 12 horizontal joints are synchronized to achieve smooth acceleration and deceleration of the body. Once the body move is completed, the task-level controller notifies the perception subsystem to acquire a new. laser range image. This enables preprocessing of the image to occur concurrently with planning and control tasks. Typically, by the time the leg and body moves have been executed, the planners are ready with a new set of moves. In this way, the Ambler achieves nearly continuous motion.

3.2.

Perception
a

From the challenges identified in Section 1 follows for a perception system that provides:

need

159
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

Fig. 3.
~

Module,s in tlze

integrated walking system.
the polygonal boundary of a region. These characteristics match the needs of the Ambler’s planning algorithms (see Section 3.3). The scene consists of a sand base with boulders 1 to 2 m tall (foreground) and a wooden ramp.

The rover must avoid stepping in unsafe areas that could cause it to lose traction or become unstable and tip over.

Self-reliant control:

by specifying

~

Limited power: The
contact.

rover

efficiency by planning
~

maximizes its power motions minimizing terrain

Rugged terrain

traversal: The rover must select favorable footholds in rugged terrain based on quantitative information about terrain properties such as elevation, slope, and roughness.

3.2.1.
The

Sensing

and Calibration

To address these

challenges,

we

have

developed

per-

ception algorithms and systems that build maps for the purpose of locomotion. The primary terrain representation is an elevation map, in which each (~, y) grid point is
labeled with the maximum terrain elevation at that point. Elevation maps are well suited for representing natural, rugged terrain, since they make few assumptions about the shape of the terrain. In addition, subsections of the map can be accessed by other system modules simply

sensor is a scanning laser rangefinder, which both reflectance and range (Fig. 6). The sensor views terrain 1 to 8 m ahead of the Ambler. We use a laser scanner because it directly recovers the environment’s three-dimensional structure, supplying 3D data more rapidly and reliably than passive vision techniques such as structure-from-motion and binocular stereo (although recent advances (Proy et al. 1993; Matthies 1992) make stereo far more feasible for planetary rovers than it was in 1987, when the decision was made to use a laser

primary

measures

rangefinder).

160
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

Fig.

4.

Graphical

user

interlace.

The sensor (a Perceptron scanner) acquires data in 256 x 256 pixel images at a rate of 2 Hz. It digitizes to 12 bits over approximately 40 m, providing a theoretical range resolution of approximately 1 cm. The measurements cover 60° in azimuth and 60° in elevation. To ensure accurate sensor data, we have developed an automatic calibration procedure that identifies the transformation between the Ambler-centered reference frame and the sensor-centered frame. The procedure moves the leg to various positions within view of the scanner and processes the reflectance image to locate the leg. The leg positions in the images and those positions computed by the Controller from the vehicle kinematics are used to compute the transformation, which minimizes the distance between pairs of corresponding points referred to the Ambler-centered frame. The technique achieves an accuracy of 2 to 7 cm with a precision no lower than 2 to 5 cm (Krotkov and Hoffman 1994).

Fig. 5. Conservative support polygon.

We selected this configuration because it is modular, extends easily to more and different sensors, decouples imaging and mapping, and manages large quantities of data.

3.2.2. The

Perception Subsystem
consists of three
one

major modules: preprocess and store images, and one to construct terrain maps (Fig. 7). Approximately 10 other modules perform data analysis and display tasks, each executing concurrently. There are many different system configurations that meet the perception needs identified at the beginning of Section 3.2.
one to

perception system acquire images,

to

Image Acquisition The Perception Imaging Manager (PIM) acquires frames of range and reflectance data, selecting either (1) real images from the rangefinder, (2) virtual images stored previously, or (3) synthetic images
a 3D graphics simulator. The PIM tags each image pair with the body pose (position and orientation), the six leg positions, the transformation relating the scanner frame and world coordinate frames (composed from

computed by

transformations derived from the calibration

procedure
161

Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

Fig. 6. Reflectance (left) and ground) and a wooden ramp.

range

(right) images.

The

scene

consists

of a

sand base with boulders 1

to

2

m

tall

(fore-

at

the bottom

comers

of the

image (Hebert

and

Krotkov
~

1992).

s pixels belonging to the image of the robot’s in the the where legs. First, predict image leg(s)

Mark

~

Fig. 7. Perception system modules.

and the Ambler’s dead-reckoned pieces of information.

pose),

and other useful

Image Preprocessing, Storage, and Access The PIM transmits the tagged images to the Image Queue Manager (IQM). The IQM preprocesses, stores, and provides access to the images. The preprocessing steps seek to filter out spurious data, and to detect range discontinuities. Figure 8 illustrates the results of preprocessing the scene shown in Figure 6.
~

appear, and what the range values should be. Then search the predicted regions, marking those pixels with range values consistent with the leg location. Identify pixels corresponding to scene points that are not connected to the ground plane. These &dquo;floaters&dquo; can occur under several circumstances documented elsewhere (Hebert and Krotkov 1992), and summarized here: ~ If the scene point lies at a distance p beyond the ambiguity interval of the sensor (i.e., farther than 40 m), then the range reported by the sensor will be p mod 40. ~ If the scene point belongs to an object that poorly reflects the infrared radiation, then the range reported by the sensor will be significantly greater than the true range. ~ If the scene point belongs to an object oriented so that the angle of incidence is small (far from perpendicular), then the range reported by the sensor will be significantly greater than the true
range.

~

Identify range discontinuities using the Canny operator (Canny 1986). The extracted edges are used in subsequent mapping algorithms to prevent interpolation between distinct objects in the scene. Mark pixels suspected to be corrupted by limitations of the particular sensor used, including internal reflections at specific locations, and a &dquo;vignette&dquo; effect (caused by the exit window) appearing

incorrectly reported range of the point causes the computed elevation of the point to be substantially different from the ground elevation. Consequently, the reconstructed scene point appears to
In each case, the
scene

float above or below the terrain. We use standard image processing techniques to extract range-connected regions. We eliminate from further con-

162
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

Fig.

8.

Preprocessed

range

image. A, Range discontinuities. B, Valid pixels shown white, corrupt pixels shown black.

sideration small regions (including regions of size one, namely, single disconnected pixels). After preprocessing, the IQM stores the processed images in a fixed-length queue, removing older images as the queue fills up. For most of the experiments, the queue size is 30, since that has empirically sufficed for the most challenging case: point turns in rugged terrain. The image queue data structure facilitates access to ordered sequences of images. Sequences are needed because the single forward-looking sensor on the Ambler cannot image obstacles either below or behind the vehicle, and must rely on previous images to accomplish tasks such as planning the trajectory of a recovering leg. The IQM is selective because transferring images is expensive: the size of the images is large (256 K per pair, plus variable-size auxiliary structures such as edge images), and many images may be required (with typical queries for 1-m2 areas, five are required for a straight-line trajectory on flat terrain, and 25 are required for a point turn over obstacles). Given a polygonal region of interest, the IQM selects only rectangular subimages that, after projection onto a ground plane, enclose or intersect the given region of interest. In typical operation, this reduces data transfer by 75% to 90% compared to the policy of transferring the entire image whenever it contains some part of the region of interest.

arbitrary reference frame to be used as origin. Typical reference frames are the current body frame, the world frame, and a future body frame (to allow for advance planning). To construct the
tion, and (3)
the map
an

queries the IQM for a sequence of subimages potentially containing information about the polygonal region. The LTM then uses the subimages, starting with the most recent, to compute the elevation of each grid point in the polygonal region. The LTM
maps, the LTM first

terrain elevation with the Locus for transforming and interpolating range data from the sensor frame into Cartesian coordinates. To summarize the Locus Method, let p be the sensed range, and let ? and B be the vertical and horizontal scanning angles of the laser beam direction corresponding to row and column position in the image. The problem of

computes and

stores the

Method,

an

efficient

algorithm

finding the elevation z of a point (w, y) is equivalent to computing the intersection of the surface observed by the sensor with the vertical line passing through (:~, ~). The basic idea of the locus algorithm is to convert the latter formulation into a problem in image space. A vertical line is a locus (curve) in (0, 0, p) space. Similarly, the range image can be viewed as a surface p 7(<~, 0). The prob=

Terrain Mapping Terrain elevation maps are constructed and maintained by the Local Terrain Mapping (LTM) module. Other modules request elevation maps,

specifying (1) a polygonal region, (2)

a

map resolu-

lem then is to find the intersection, if it exists, between a curve parameterized by ? and a discrete surface. Since the surface is known only from a sample of data, the intersection cannot be computed analytically. Instead, we must search along the curve for the intersection point (we refer interested readers to Kweon and Kanade [1992] for details of the search). The LTM assigns one of three labels to each point in a rectangular grid enclosing the specified polygon:

163
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

Unknown, for those cells outside the polygon, outside the field of view of all images, or containing pixels marked as invalid by the preprocessing steps. 2. Occluded, for those cells occluded by other objects. An (x, y) location in the map is in an occluded area if its locus intersects the image at a pixel that lies on an occluding edge. We implement this idea by first detecting edges in the range image using the Canny operator. Then, when we apply the Locus Method and observe that the locus of a given location intersects the image at an edge pixel, we mark that location as lying in an occluded area, and compute an upper bound on the elevation of the occluded terrain. 3. Known, for all other cells.
9 illustrates the elevation map computed from the range image of Figure 8. This map contains points labeled known and occluded.

1.

delete less recent data. In one typical trial, after acquiring 100 images, memory usage levels peaked at 1.6 MB for PIM, 2.8 MB for LTM, and 30.5 MB for IQM (with queue size 30). After this, the perception system maintained essentially constant memory utilization, thus demonstrating the effectiveness of memory management. In summary, the results show that the perception system constructs quantitative models of terrain geometry that enable power-efficient locomotion in rugged terrain. 3.3.

Planning

We have developed automated planning algorithms for the Ambler that address the three main challenges identified in Section 1 as they relate to the planning system:

1.

Figure

Self-reliant control: Given a path to follow, the rover must autonomously plan leg and body
moves

3.2.3.

Performance

Table 1 records perception system statistics gathered from several representative walking trials. The large volume of images and maps processed indicates the robustness of the system. We found from these trials that taking a single step requires approximately 20 s of perception system processing, which involves examining between 5 and 28 range subimages in order to compute elevation values for some 1700 points, on average. Breaking the timing down further, we find that for SPARC 2 workstations, image acquisition takes about 1 s, image preprocessing and storage requires about 10 s, and construction of elevation maps takes about 5 ms per point. &dquo;Distance&dquo; represents the distance traveled by the robot during the trial. The results vary because the terrain and software modules vary between trials. For example, in the 46-m run in hilly terrain, a module planned vertical body motions, computing more map points than in the 68-m run in non-hilly terrain, during which that module did not
execute.

safe and effective (i.e, maintain the path). 2. Limited power: The planner should choose moves that minimize energy expenditure. This includes minimizing leg and body travel and avoiding unnecessary terrain collisions. 3. Rugged terrain: The algorithms must enable the rover to climb hills, traverse rock-strewn terrain, and to cross meter-tall and meter-wide obstacles (such as boulders and trenches).
that
are

good

progress

along

One
tween

measure

the

of map accuracy is the difference becomputed elevation and the elevation deter-

mined by encoders on the Ambler’s legs. According to this measure, we find that the map accuracy varies from step to step and from trial to trial, but never strays far from the scanner precision of 10 to 15 em. This accuracy is sufficient for the Ambler, whose feet are 30 cm in diameter. As the Ambler walks, images and maps consume more and more memory. As a countermeasure, the perception system utilizes memory management routines that detect memory saturation, reclaim storage for new use, and

All three challenges indicate the utility of a deliberative approach to planning leg and body moves. In particular, for the type of remote, rugged terrain walking that we address, the effects of ill-considered decisions can be catastrophic. Thus, to provide for safe, powerefficient movements, the planning algorithms utilize detailed models of the vehicle kinematics, the terrain, and vehicle-terrain interaction. One potential problem with deliberative planning of moves is the computation involved in searching for acceptable moves. This is exacerbated in the Ambler, since .. a large number of moves are possible from a given pose. The planning algorithms attempt to minimize the amount of search needed by adding constraints to the rover motion, such as always using a circulating gait. To date, our research in autonomous planning has concentrated on path following: the rover is constrained to walk along an arc of a circle: if the arc has large radius, the path is nearly straight; if the arc has zero radius, the rover turns in place. We have developed a hierarchy of three planning algorithms-gait, footfall, and leg recovery-to handle path following. 3.3.1. Gait

Planning
chooses the sequence of

Gait

planning

moves

to advance the rover

along

a

leg and body given path. Typically,

164
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

Table 1.

Perception System Statistics in Four Separate Trials

Fig.

9. Elevation map.

such as tripod and Waldron gaits (Brooks 1989; Song 1989). However, due to the mobility of the Ambler and the extreme terrain it has to traverse, we developed a planner that uses a free gait, one in which the choice of which leg to move is made step by step, depending on current kinematic and terrain constraints. The planner also capitalizes on the unique features of the Ambler to implement a circulating gait, one in which the rear-most legs move through the body cavity to become the new front-most legs (Fig. 10) (Bares and Whittaker 1994; Wettergreen et al. 1990).
use a

walking

robots

fixed

gait pattern,

or wave

1. We have also developed a planner for Ambler to walk from side to side.

a

crab

gait,

one

that enables the

radius and angle that (the angle can be positive or to walk forward or backenable the rover to negative, The basic ward). walking cycle is to alternate moving the so that it remains oriented tangent to the arc and body then moving the leg that most constrains subsequent body motion. For arc radii less than the tread width of the Ambler (about 2.5 m), the gait planner first circulates the rear leg on one stack to the front, and then circulates the front leg on the other stack to the rear. In this way, the Ambler can turn in place by having the legs on one stack move retrograde with respect to the legs on the other stack. The gait planner utilizes two constraints to determine the extent of the body move. The first constraint is based on the kinematic limits of the legs. Given that the feet

The

input

to

the

gait planner

is

a

describes

an arc

to traverse

165
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

Fig. 10. Circulating gait.

166
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

Fig.
are

1l. Stack

reachability constraint.
can

fixed, the planner determines how far each stack

along the arc before reaching a kinematic limit (Figure 11A). The second constraint is based on stability. To be statically stable, the rover’s center of mass must lie within the support polygon formed by the convex hull of the feet. For added safety, we insist that the Ambler always lie within the conservative support polygon (CSP), which is defined as the intersection of all five-legged support polygons (see Fig. 5) (Mahalingam and Whitmove

taker 1989). Thus, if the Ambler remains within the CSP, any one leg can fail, and the vehicle will still remain statically stable. The gait planner finds where the body travel intersects the leading edge of the CSP and uses this as an additional constraint on body motion. The minimum motion determined by the kinematic and support constraints is then chosen as the next body move. This planning suffices for movement in the horizontal plane. To plan vertical movements, the planner obtains a terrain map from the perception system of a region in the direction of travel. It finds the maximum elevation in the region and, if needed, commands a vertical move (lift or lower) to keep the Ambler within a fixed window above the terrain (typically, 50 to 90cm). This decoupling of horizontal and vertical body motion planning is possible because the Ambler always walks with a level body motion (parallel to gravity) and its legs decouple horizontal and vertical motion. Thus, changing the body elevation has no effect on the kinematic limits of leg travel or on the static stability of the rover. After commanding body motion, the planner then selects the leg move that will afford the greatest subsequent body progress. This is done by determining the maximum body movement, assuming the leg is not fixed to the ground. In most situations, the planner considers the rearmost legs on each stack; however, for tight turns (arc radii less than the distance between the body and

stack centers, or about 2 m), one of the stacks moves in retrograde motion (Fig. 11B), so that the planner must alternate moving the legs on one stack from rear to front, and the legs on the other stack from front to rear. There are a number of geometric constraints that come into play in determining where to place the feet. The kinematic limits of the leg define a torus outside which the leg cannot reach. In addition, the leg must be placed so that it does not collide with the current frontmost leg, nor should it be placed within the current path of the body (Fig. 12). Finally, there are constraints needed to ensure the feasibility of subsequent movements: the leg must be placed far enough forward so that a subsequent leg move on the opposite stack keeps the body within the CSP, and the leg must not be placed so far forward that subsequent leg moves on the same stack become kinematically infeasible. These kinematic constraints define an area within which all footfalls are geometrically feasible. If the area for a leg is insignificant, the planner tries moving the leg on the other stack. If there are no feasible moves on either stack, the planner attempts to shuffle the legs and tries to plan from there. To shuffle legs, the planner moves legs forward, backward, and side to side (without circulating through the body) so that the legs are placed close to a standard configuration. Although in principle up to five legs might have to be moved, in practice we have observed that shuffling usually involves moving one or two of the front or middle legs. Shuffling of the legs is needed, on average, every 30 steps or so. 3.3.2.

Footfall Planning

Given the region of geometrically feasible footfalls determined by the gait planner, the task of the footfall planner is to find the best terrain patch within that region, in terms of its ability to provide stability and traction. One problem is the difficulty of operationalizing those criteria. While flat, smooth areas are obviously ideal and steep, rough areas tend to provide the worst footing, it is unclear how to quantify the areas in between. We tried several methods of evaluating footfall quality, including hand-coded rules and nonlinear regression techniques. We eventually settled on a neural network learning scheme, which was found to produce consistently the best results (Hsu and Simmons 1991). The purpose of the neural network learning scheme is to estimate footfall quality of the terrain based on features such as slope, roughness, and curvature. The neural net learns an evaluation function that combines these features. It is trained off-line using human-supplied indications of footfall quality (e.g., &dquo;good&dquo; or &dquo;very bad&dquo;) in a variety of terrain. The training data are the pairs of locations where the numerical evaluation produced, using the current set of weights, differs from the human preferences.

167
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

Fig. 12. Constraints

on

geometrically feasible footfalls.
as an error

The difference in the evaluations is used
to

term

weights using backpropagation 1988). This method of using a neural network to combine precomputed features (rather than operating directly on the raw data) has proven quite effective, both in learning speed and on-line operation. In particular, the features provide sufficient structure to make the learning tractable
et al.

update (Rumelhart

the network

kinematic and geometric model of the Ambler, information on maximum joint velocities. The handles both circulating and noncirculating algorithm recoveries (the latter are used primarily when shuffling

explicit
as

well

as

legs).

and are fairly easy to compute from the terrain elevation maps produced by the perception system. Initially, we considered refining the net weights on the fly, as the Ambler gained experience walking, but the initial function learned proved adequate enough, and so the adaptive approach was not actively pursued. On-line learning techniques remain a possibility, however, especially if the rover would be exposed to novel environmental conditions (such as might occur on Mars).

trajectory is determined, the planner projects &dquo;envelope&dquo; of vertical motions along the trajectory. The envelope assumes that the leg raises/lowers at full speed while traveling horizontally. Purely vertical moves are needed only when the envelope is projected
Once
a

horizontal

an

intersect the terrain, or if needed to clear the top of the Ambler’s body arch. Although this algorithm is not necessarily optimal (a longer horizontal trajectory might result in significantly less vertical travel), in practice the moves produced by the leg recovery planner are very
to

good.
3.3.4. Remarks

3.3.3.

Leg Recovery Planning

While the

The task of the leg recovery planner is to plan energyand time-efficient trajectories for the legs. This involves minimizing joint movement (especially the slow vertical actuators) and maximizing the amount of time all three leg joints are actuating simultaneously. The planner must also ensure that the legs do not collide with the terrain or any part of the rover. In general, this is a complex three-dimensional search problem. An early version of the leg recovery planner did in fact search a 3D space to find optimal moves (Krotkov et al. 1990). This proved to be very expensive, both in terms of planning time and in the demands it placed on the perception system. The current leg recovery planner minimizes search by decoupling the planning of horizontal and vertical motions. The planner first finds a trajectory in the horizontal plane that minimizes (horizontal) joint travel while avoiding leg-leg and leg-body collisions. The planner uses an

circulating gait and independently controllable the Ambler advantages in efficiency and mobillegs give for the Ambler is significantly more complex ity, planning than for other walkers, due to its many degrees of freedom and relatively narrow front-to-back stability margin (Bares and Whittaker 1994). On the other hand, in several situations we have been able to take advantage of the decoupling of horizontal and vertical motions afforded by the orthogonal legs to simplify planning algorithms and to reduce search. Overall, the planning system is very robust and reliable, enabling Ambler to autonomously walk along varied paths and through varied terrains (see Section 4). The Ambler’s deliberative mode of walking contrasts sharply with the reactive approaches taken by most other researchers (Brooks 1989; Pfeiffer et al. 1991; Raibert 1986). The main advantage of the deliberative approach is that by carefully analyzing kinematic and terrain constraints, the Ambler can produce more reliable and

168
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

efficient moves. Reliability is increased by decreasing the chance of tipover or placing feet in unstable locations. Efficiency is increased by minimizing actuator motion and minimizing the number of terrain collisions. The main disadvantage of the deliberative approach is that it is computationally intensive: the Ambler planners take 30 to 40 s per step (of which about 75% of that time is spent by the perception system creating terrain maps for the various planners). This is acceptable for the Ambler due to the slow top speed of the mechanism: The planning is still about 50% faster than the cycle time of body/leg moves. By planning one step while executing the previous step (see Section 3.4.2), the Ambler planning system can provide a continual stream of moves to the real-time control system, demonstrating that computation does not create a bottleneck for the Ambler. With a faster, mechanically simpler rover, we would probably change our planning strategy, relying more on reactive (although not totally reflexive) control.

maintains the dead-reckoned position, and communicates with other modules. The other executes horizontal and vertical body trajectories at 10 ms intervals.

trajectories,

3.4. Control

The Ambler system uses two types of control: real-time and task-level control. Real-time control is used to interface with the rover: driving servo loops, reading internal sensors, and maintaining the dead-reckoned position. Task-level control is concerned with integrating perception, planning, and real-time control into a concurrent, distributed system. The task-level control manages the system’s resources, schedules and synchronizes tasks, and provides for execution monitoring and error recovery.

.3.4.1. Real-Time Control
The

design of the directly addresses
tion l: l.

Ambler’s real-time control system the three challenges identified in Sec-

Self-reliant control: The rover must autonomously react to and safeguard against unanticipated electromechanical conditions such as amplifier faults, and unexpected environmental situations, such as

soil failure and excessive tilt. 2. Limited power: The rover must faithfully execute the leg and body trajectories planned to avoid obstacles to avoid wasteful transfer of energy to the terrain. 3. Rugged terrain traversal: The rover must move its legs with sufficient precision to be able to step in tightly constrained spaces (e.g., between two

boulders).
The Controller
runs on two

68030 CPU boards in

a

real-time, multitasking environment. One CPU generates

Motion Control and Safeguarding The Controller’s main task is to move the legs to a given position and to move the body to a given pose. Given a commanded body position, the Controller decomposes the motion control task into two parts: a planar translation and/or rotation followed by a vertical lift or lower. For the planar motion, the Controller computes the horizontal joint motions that simultaneously translate and rotate the body to achieve the commanded horizontal position. It executes a horizontal body move by first locking the vertical joints and then servoing the 12 horizontal joints to achieve smooth acceleration and deceleration of the body. For the vertical motion, the Controller follows the same scheme, but servos only the six vertical axis joints. Given a path for the leg to travel, denoted by a series of waypoints, the Controller generates a sequence of joint positions beginning with the current leg position and ending with the final waypoint position. It then interpolates those joint positions, producing a trajectory that is linear in joint space. In executing this trajectory, the Controller coordinates the three leg joints so that all motions start and end simultaneously, as with the body move. During execution, the force sensor is set to trigger an interrupt if either normal or lateral forces exceed threshold values, signifying terrain contact. The Controller treats the interrupt either as the successful completion of a leg move or as an unexpected collision, depending on where in the trajectory it occurred. The Controller includes many safeguards to protect the Ambler. Before committing to execute a move, the Controller performs a kinematic and geometric analysis of the move to check that the move will not exceed joint limits, that leg motions will not collide with other parts of the mechanism (in particular, that the leg will pass safely through the center of the body while executing a circulating gait), and that the vehicle will remain statically stable at all times during the move. If any unexpected situations occur during execution, such as premature ground contact, the Controller halts all motion and engages the brakes. In addition, the Controller monitors inclinometers and automatically levels the robot when the body tilt exceeds a threshold value. This also helps safeguard against failure of the force sensors-if a force sensor fails to register ground contact and the leg is driven into the ground, at some point the tilt monitor will register and stop motions before the Ambler tips itself over. For further safeguarding, a hardware safety circuit sets the brakes and shuts down all motions if it detects anomalies such as servo motion or amplifier faults.

169
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

Dead-Reckoning Many exploration
or

missions require benefit from estimates of robot pose and course (sequence of poses). For example, without course estimation it would be impossible to produce a map of an area wider than the sensor field of view, or to achieve such objectives as searching exhaustively for ice in a specified region. For such missions, dead-reckoning is a widely used method that identifies the pose of a vehicle by integrating its motion. We have developed a dead-reckoning algorithm that increases the robot’s capability to address the challenge of self-reliant control. To formulate the problem, we define a stationary world reference frame W, and a body frame ,13 attached to the Ambler body, which moves with respect to W. Let x~v,z denote the position of foot i in W. Let xb,i denote the position of foot i in 13; these positions can be computed using the mechanism kinematics. We assume that the Ambler can be treated as a rigid body, which means that the feet do not move unless commanded to do so. Then the dead-reckoning problem amounts to finding the rigid body transformation (the rotation matrix R and the translation vector t) such that

we computed the dead-reckoned pose and measured the ground truth pose by using a surveying device. For each move we recorded the dead-reckoned and ground truth poses. Figure 13 illustrates the results of one trial with 12 body advances covering 6 m along a straight line. The

command,

figure plots

the

planar error

b~ + by, where the 6 terms

represent the component-wise differences between deadreckoned and ground truth poses. These data indicate that the dead-reckoning error u is 2% of the distance traveled. Given the high precision of the prismatic and rotary joints and the high encoder resolution, this accuracy is lower than expected. Further analysis of the data show that systematic error dominates random error: dead-reckoning &dquo;thinks&dquo; that the body travels a smaller distance than the surveying device measured. We believe the source of the systematic error to be an incomplete kinematic model of the Ambler, one that does not adequately address factors such as small differences between leg dimensions or structural deflection. To reduce the systematic error, we could adjust the deadreckoned planar pose by adding (u cos B, u sin 0), where 9 is the heading. With this correction, we anticipate accuracy better than one percent.
3.4.2. Task-Level Control Task-level control involves the integration and coordination of perception, planning, and real-time control to produce a complete robotic system. The Ambler’s use of task-level control effects two of the three challenges described in Section 1.
~

We seek

a

solution that minimizes the

squared

error

where ej x~j &horbar; Rxb,j - t, and the wj are weights on the observed positions. We implemented a solution to this minimization problem in three steps (Roston and Krotkov 1992):
=

Identify feet that have slipped and prevent them from being used in further computation by setting w to zero. Foot slippage is detected using the constraint that the distances between feet should not be affected by a body move: by noting the distances before and after a move, it can be determined which feet might have slipped relative to one another. 2. Solve for the rigid body transformation that best transforms foot positions in t3 to W, using a technique developed by Matthies (1989), based on singular value decomposition. 3. Update foot positions, if necessary, based on the new body pose and the current leg joint angles. Ideally, no update should be required, but in practice, the least-squares solution may cause discrepancies between the current and stored foot positions.
To test the implementation of dead-reckoning, we conducted trials in which we commanded the Ambler to advance a specified distance. After execution of the

1.

Self-reliant control: The rover must be able to detect and recover from a wide range of exceptional conditions, ranging from hardware faults to situations that the normal planning software cannot handle.
Limited power: Efficient use of the rover’s resources minimizes overall power consumption. This includes reducing the idle time, since there is a fixed overhead incurred just standing still, which argues for use of a concurrent, distributed software architecture.

~

The Ambler subsystems are integrated using the Task Control Architecture (TCA). The architecture provides a language of communication and control constructs for coordinating distributed mobile robot systems, and a library of utilities to facilitate development of concurrent robotic systems (Simmons 1990, 1994). The communication constructs support coarse-grained message passing between processes, with TCA handling the tasks of encoding and decoding message data and routing messages and responses to the appropriate processes. The TCA control

170
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

Fig. 13. Dead-reckoned position error. The points represent the difference between the dead-reckoned and ground truth body positions in the plane of travel. With each advance, the error increases by about two percent of the distance
traveled.

support hierarchical planning, task and resource scheduling, monitors, and exception handling. The control constructs are designed around the concept of hierarchical task trees, which serve as the TCA representation for plans (Fig. 14).
constructs

previous one. By having planning and execution occur concurrently, the Ambler system can walk nearly continuously, doubling the average walking speed compared with the original sequential sense/plan/act system (Simmons 1994). In a similar manner, we use TCA control specify when laser scans should be initiated and to indicate that processing of range images can occur concurrently with planning and execution. Figure 15 shows a Gantt chart of the resource utilization of the various modules. Utilization of the planning and perception modules increased by about 33% over the original sequential system, while the real-time controller was busy 95% of the time. The average walking cycle dropped from 80 s to about 60 s. This reduces power consumption per distance traveled, since many components (e.g., computers and amplifiers) draw significant current
constructs to
at

Concurrency

Besides

encoding hierarchical

TCA task trees encode temporal constraints between subtasks. The temporal constraints enable the specification of partial orderings between subtasks. For example, the task tree in Figure 14 indicates that to walk along an arc (following the algorithm described in Section 3.1), the rover must take a sequence of steps. Each step consists of recovering the leg, moving the body, and recursively taking a sequence of steps (until the desired goal position is reached). The &dquo;sequential achievement&dquo; temporal constraints indicate that subtasks must be executed in order; in particular, all command messages (the leaf nodes in one subtree) must be handled before any of the commands of the subsequent subtask
can

goal/subgoal relationships,

all times.

begin.

&dquo;delay planning&dquo; constraint indicates that a goal message cannot be handled (i.e., decomposed into subtasks) until the previous task has been achieved. Thus, due to accumulated dead-reckoning error we specify that the plan for walking along one arc should not be planned out until the previous arc has been traversed. On the other hand, the absence of a &dquo;delay planning&dquo; constraint between the &dquo;moveBody&dquo; and &dquo;takeSteps&dquo; subtasks indicates that the system can plan out one step while executing the

A

Error Recovery To be self-reliant, an mobile robot system needs to react to environmental changes in an appropriate manner. In particular, it must determine when its present course of action is failing, and try alternative plans. The task control architecture facilitates building such self-reliant systems

Monitoring and
autonomous

its monitoring and exception handling constructs. The Ambler system utilizes several strategies to provide self-reliance: use of redundant monitoring and sensing; use of a hierarchy of exception handlers; and incrementally increasing reliability by layering monitors and exception handlers.

through

171
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

Fig.

14. Task tree for Ambler walk planning.

Redundancy is important in constructing reliable systems-single points of failure should be avoided if at all possible. This is manifested in the Ambler system partly through the use of redundant hardware and software safety checks during critical operations, and partly through the use of redundant sensing and monitoring. For example, the planning code uses a model of the Ambler to plan moves that fall within the kinematic limits of the
mechanism. The real-time controller uses a similar geometric model to ensure the validity of moves prior to executing them. Finally, hardware limit switches will be triggered in cases where the software fails to limit the moves. Similarly, the real-time controller monitors the force sensors in the feet to detect ground contact. Occasionally the sensors fail, causing the leg to jack up the body as it drives into the ground. This situation is detected by monitoring the inclinometers: if more than 1° of tilt is observed, all motion is halted and the body is automatically releveled. An organizing principle used in the Ambler software system is to keep planning and exception handling functions separate, using separate modules for each, but with the exception handlers organized into a hierarchy similar to the planning hierarchy. These principles of separating and hierarchically structuring exception handlers are directly supported by TCA. TCA provides control constructs to associate monitors and exception handlers with nodes in the task tree. When a module raises an exception or a monitor detects a particular condition, TCA searches up the task tree to dispatch the closest han-

dler. If that handler cannot deal with the error, the search continues up the tree. In this way, exception handling is kept context dependent and handlers are tried in order of decreasing specificity. This usually results in the lower levels handling the majority of exceptions, with minimal impact on the overall walking plan. Figure 16 shows the positions in the task tree of some of the monitors and exception handlers used in the Ambler system. Before every move, a stability monitor checks whether the move keeps the Ambler’s center of

gravity within the support polygon of the legs, aborting the walking cycle if the move might cause the Ambler to tip over. After every footfall, a monitor analyzes the
to determine if the foot is in unstable configuration (i.e., if the point of ground contact is very off-center). If so, the leg is moved 10 cm at a time away from the point of contact until a stable footfall is found. During leg motion, the controller monitors the force sensor and stops motion if contact is detected. An exception handler moves the foot up and away from the point of contact and then commands the controller to finish the leg move. The controller also detects hardware faults (e.g., amplifier faults, servo faults, limit switches). For faults that might be intermittent, the Ambler system retires the move, giving up (and cancelling all active tasks) if the fault continues after several

force/torque measurements
an

attempts.

Finally, there are several exception handlers to deal with failures of the planners to find suitable plans. If

172
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

Fig.

15.

Timings of Ambler modules during

concurrent

walking cycle.

173
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

Fig. 16. Task
the
to

tree

with monitors and

exception

handlers.

gait planner fails, the first exception handler tries replan with the latest robot pose (since the system plans in advance, sometimes the planned and actual poses differ). If this fails, the system shuffles the legs, putting them into a standard configuration, after which the normal planning cycle takes over. If that fails, the walking tasks are terminated, and the user must input a new path to
traverse.

conditions, etc. The task control architecture provides support for controlling interactions, such as ules,
race

managing physical and computational resources, synchronizing subtasks, and monitoring and handling exceptional
situations. Besides providing a set of commonly needed control constructs, the system development methodology supported by TCA facilitates dealing with interactions. First, all control decisions are encoded explicitly in the module software and maintained explicitly by TCA. This provides for greater predictability and understandability of what the system will do in various situations: exactly how subtasks are temporally related, under which contexts monitors and exception handlers are active, etc. Second, TCA enables new functionality to be added incrementally, without modifying existing code. For example, with the Ambler we first developed a sequential sense/plan/act system (which was easier to test and debug) and then added concurrency by removing temporal constraints (Simmons 1994). Similarly, we added new monitors and exception handlers incrementally as our experimentation with Ambler uncovered limitations in the way the robot reacted to unexpected situations (Simmons

These monitors and exception handlers (and there are several others, as described in Simmons 1992), together with those implemented in the real-time controller (described in Section 3.4.1) provide the software system with enough reliability to walk many steps without human intervention. In particular, the Ambler has walked continually over 1000 steps (over half a kilometer). Exceptional situations are detected on the average of once every 10 to 20 steps, depending on the ruggedness of the terrain and the curvature of the path. Only on rare occasions is control passed back to the human operator-most situations are handled by the controllers. Even on those rare occasions, however, the Ambler system safely halts motions and maintains itself in a stable configuration while awaiting further input from humans. This is exactly the type of behavior required of a spatially and temporally remote vehicle, such as one operating on the Martian

1992).

surface. Remarks One of the more difficult tasks in developing concurrent, distributed mobile robot systems is dealing with interactions: interactions between the vehicle and the environment and interactions among subsystems. These include problems of handling changes and uncertainty in the environment, resource contention between mod-

All this flexibility comes at a price, however, since TCA must maintain the task trees and track all message traffic in order to assure that the desired control decisions are carried out. While there is the potential for a centralized system bottleneck, in practice we have not found this to be a problem. For the Ambler system, the TCA central control module is active only about 3% of the time. We view this as a small price to pay for the flexibility and ease of use afforded by using the architecture.

174
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

4. Autonomous

Walking Results

The Ambler autonomous walking system has been tested extensively over the past several years, in both indoor and outdoor trials. This section presents results from a representative sample of the many trials, including indoor navigation over rugged terrain and outdoor, long-distance,

long-duration, autonomous walking. A typical trial begins by executing perception, planning, and control processes on the on-board computers.
For
are

convenience, the standard outputs of these processes

displayed on windows on off-board workstations. A human operator enters a path as a sequence of arcs, and issues the command for the Ambler to start walking. The Ambler then operates autonomously, planning and exevery footfall, leg move, body move, leveling and any other action or reaction needed. To date, the Ambler has walked autonomously a total of over 4 km, much of it over rugged, difficult terrain. Table 2 reports statistics of several walking trials, which were selected to indicate the progressive escalation of challenges and capability. In the table, the column labeled &dquo;planar travel&dquo; indicates the horizontal distance traveled by the Ambler body, but does not include vertical body motions. The &dquo;leg travel&dquo; column reports the sum of the planar distances traveled by the legs, measured from pickup to set-down. The total leg distance can be greater than six times the body travel during trials in which the Ambler is executing many point turns, since in that maneuver some legs travel in retrograde motion (see Section 3.3.1 ). Most of the leg travel occurs during circulation. Walking time includes the time required for movement, sensing, mapping, planning, and processing; it excludes idle time due, for instance, to debugging. Average walking speed over all types of terrain is 35 cm/min. Walking speed for straight-line, benign terrain is about 4&copy; cm/min.

In the figure, the thin lines indicate the course the center of the Ambler’s body for one complete circuit. The black triangle indicates one randomly selected body pose obtained during the trial. Other trials typically resulted in somewhat different courses, due to changes in the terrain and exact starting location of the robot. Completing more than two circuits during the trial, the Ambler turned nearly 9 complete revolutions, thus devoting a significant fraction of the trial to turning rather than to advancing. The two circuits were different in the sense that the robot did not take the same step twice.

(Fig. 18).

followed

by

ecuting

maneuver,

4.2. Outdoor Trials
A number of trials were performed outdoors. These differed from the indoor trials primarily in that we were able to test the ability of the Ambler to traverse significant slopes (tens of degrees over multiple vehicle lengths) and to operate autonomously for long distances (up to 0.5 km
at
a

time).
one

4.1. Indoor Trials
For indoor trials, the Ambler operated on obstacle courses fashioned from 40 tons of sand, 20 tons of boulders, a 30° wooden ramp, and various other objects (Fig. 17). The courses typically included rolling, sandy terrain with several boulders 1 m or taller, approximately 10 boulders 0.5 m tall, a ditch, and a ramp. The largest of the boulders was 1.5 m tall, 4 m long, and 2 m wide. With such materials, the obstacle courses pose significant barriers to locomotion. We know of no other robot that could surmount all of the obstacles in the course. Traversing a variety of these obstacle courses, the Ambler has demonstrated long-term autonomous walking. In one trial, the Ambler took 397 steps and traveled about 107 m following a figure-eight pattern, each circuit of which covers about 35 m and 550 degrees of turn

set of outdoor trials, the Ambler operated’ in a lot strewn with wooden obstacles such as boxes, parking and ramps. In one of these trials, the Ambler pyramids, took 100 steps along a gently curving arc, traveling about 25 m over a variety of obstacles. In another trial, the Ambler walked in the parking lot at night, without lights, since the laser rangefinder does not require ambient illumination. In fact, we observed the range images to be noisier during the day, because the signal-to-noise ratio is higher without ambient illumination. For another set of outdoor trials, the Ambler operated on rolling, grassy terrain (Fig. 19). The site was a field located within a hilly, wooded area at an industrial park. Although this site did not contain obstacles like those encountered in the indoor trials, the site posed its own challenges: steeper slopes and side slopes, as well as soft

For

ground.
In the longest outdoor trial, the Ambler took 1219 steps, traveling 527 m horizontally and 25 m vertically. The robot followed a meandering course, first climbing a hill and descending it, then roughly following an isoelevation contour for 250 m, executing a point turn of roughly 7r radians, climbing a bit to a higher elevation, and then following an isoelevation contour back to the starting region. While this course is simpler than the indoor figure-eight pattern (Fig. 18), because it involves less turning and no boulders, the outdoor trial is notable for both the length and duration (over 20 hours) of autonomous operation. In addition, the Ambler traversed rather steep slopes: it ascended and descended a 30% grade and traversed side slopes of up to 15% grades.

175
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

Fig. 17. Ambler traversing induo? obstacle course. Ambiet- ori sandy terrain with meter-tall boulders (under legs and body), ditches (the center leg on the far stack is standing in one), and ramp (lower right).

Fig. 18. Top

view

of figure-eight

circuit. Boulders

are

drawn gray. Units

are

meters.

176
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

Table 2. Statistics From Selected

Walking Trials

*

The dash indicates that this data

was

not recorded.

Fig. 19. Ambler walking 527 m in field.

177
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

4.3. Remarks

problem.
are

In

particular,

the resultant system is
are

quite

de-

Average walking speed over these trials, including all computation, is 35 cm/min (typical body moves travel about 50 cm). Moving the mechanism is the main limitation to the speed. During operation, the real-time
controller is active about 80% of the time, while the and perception subsystems are each active about 50% of the time, and the centralized task-level controller is active only about 3% of the time (the total is greater than 100% because operations occur concurrently). The results of the indoor and outdoor walking trials show that the approach we adopted to control the Ambler meets the challenges identified in Section 1:

liberative, where actions

planners

~

Self-reliant control: The approach meets this challenge, since the integrated walking system exhibits a high level of autonomy in planning and executing motions (e.g., traversing a specified path), reacting to unsafe conditions (e.g., leveling), learning good footfalls on the basis of past experience, and operating for extended periods. Still, there was some
manual intervention in the form of restarting proand occasionally over-riding a default value. Limited power: The approach meets this challenge by reducing unwanted terrain contact to a negligible (but nonzero) level. Thus, the system transfers far less energy to the terrain than would a purely reactive or purely randomized robot. Rugged terrain traversal: The approach enables locomotion over challenging obstacle courses, soft ground, and significant slopes and side-slopes.
cesses

planned out in advance the terrain and the vehicle’s kinematics and geometry, and moves are checked multiple times by different modules for safety prior to execution. We believe that this approach to walking is well suited to meeting the three challenges stated above. For reasons of reliability, we want the robot to avoid making potentially hazardous moves; for reasons of efficiency, we want the robot to take steps that minimize transfer of energy to the environment and maximize progress along the prescribed path; for reasons of rugged terrain traversal, we desire that the robot accurately perceive its environment and take it into account when walking.
price, however: It is both computationally perceptually intensive. For the Ambler, this is not a problem. Since the mechanism is inherently quite slow (for reasons of power efficiency [Bares and
This

highly goal directed, steps using explicit models of

approach
and

carries

a

~

.

5. Conclusions
This article has presented a robotic system to control the six-legged Ambler planetary rover. The approach presented here integrates perception, planning, real-time control, and task-level control to navigate the Ambler, reliably and autonomously, over long distances and rugged terrain. These are capabilities that are essential for operating in remote, natural environments, such as on Mars.
~

Whittaker 1994]), the system has sufficient time to perceive and plan while the controller concurrently executes steps. For faster robot mechanisms, there is a trade-off to be made. In general, we would advocate our deliberative approach to walking for applications in which reliability and safety are more important than speed, and/or if the mechanism will typically be operating in rugged or hazardous environments. The research reported here is continuing. We are striving to increase the range and reliability of autonomous walking systems by including more monitoring and error recovery strategies in both the low-level controller and higher level planners. We are also extending system autonomy to higher levels of cognition, including route planning and global navigation, and are trying to better characterize our perception, planning, and task-level control algorithms. The aim is to produce a walking system capable of multikilometer, multiday, autonomous operation in rugged, natural environments, whether on Earth or on other planets.

own resources

Self-reliant control: The rover must depend on its for planning, taking actions, and maintaining its safety and integrity.

Acknowledgments
members of the planetary rover project have contributed to the results reported here. In particular, we acknowledge the efforts of Red Whittaker, John Bares, Brian Albrecht, Christopher Fedor, Regis Hoffman, Henning Pangels, Gerry Roston, and David Wettergreen. This research was sponsored by NASA under grant NAGW1175.

~

~

Limited power: The rover must carry its own power source, forcing it to make energy efficient moves. Rugged terrain traversal: The rover must be capable of traversing a wide variety of terrain, to get to

Many

points
These

of

geologic

interest.
our

challenges

have influenced

approach

to

the

178
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

References

Angle, C.,

planetary rovers. Workshop on Intelligent Robots and Systems, Tsuchiura, Japan, pp. 383-388.
Proc, IEEE Int.
tonomous

and Brooks, R. 1990. Small

Bares, J., and Whittaker, W. 1993. Configuration of auwalkers for extreme terrain. Int. J. Robot.
Res.

2(6):535-559.
a

Brooks, R. 1989. A robot that walks: Emergent behavior
from

carefully

evolved network. Neural

Computation

A. 1989. Fast, cheap, and out of control: A robot invasion of the solar system. J. Br. Interplanet. Soc. 42(10):478-485. Brooks, R., Maes, P., Mataric, M., and More, G. 1990. Lunar base construction robots. Proc. IEEE Int. Workshop on Intelligent Robots and Systems, Tsuchiura, Japan, pp. 389-392. Burrough, P. 1981. Fractal dimensions of landscapes and other environmental data. Nature 294:240-242. Canny, J. F. 1986. A computational approach to edge detection. IEEE Trans. Pattern Anal. Machine Intell.

1(2):253-262. Brooks, R., and Flynn,

ration. Proc. Int. Conf. Advanced Robotics, Tokyo, Japan, pp. 109-114. Hirose, S., Yoneda, K., and Arai, K. 1991. Design of prismatic quadruped walking vehicle Titan VI. Proc. Int. Conf. Advanced Robotics, Tokyo, Japan, pp. 723728. Hodgins, J., and Raibert, M. 1991. Adjusting step length for rough terrain locomotion. IEEE Trans. Robot. Automation 7(3):289-298. Hsu, G. T., and Simmons, R. 1991. Learning footfall evaluation for a walking robot. Proc. Machine Learning Workshop, Chicago, IL. Ishino, Y., Naruse, T., Sawano, T., and Honma, N. 1983. Walking robot for underwater construction. Proc. Int. Conf. Advanced Robotics, pp. 107-114.

Kemurdjian, A., Gromov, V., Mishkinyuk, V., Kucherenko, V., and Sologub, P 1992. Small marsokhod configuration. Proc. IEEE Int. Conf. Robotics
and Automation, Nice, France, pp. 165-168. Krotkov, E., and Hoffman, R. 1994. Terrain mapping for a walking planetary rover. IEEE Trans. Robot.
Automation

10(6):728-739.

8(6):679-698.
Chatila, R., and Laumond, J.-P. 1985. Position referencing
and consistent world modeling for mobile robots. Proc. IEEE Int. Conf. Robotics and Automation, St. Louis, MO, pp. 138-145. Chatila, R., Alami, R., Lacroix, S., Perret, J., and Proust, C. 1993. Planet exploration by robots: From mission planning to autonomous navigation. Proc. Int. Conf. Advanced Robotics, Tokyo, Japan, pp. 9196. Chun, W., Price, S., and Spiessbach, A. 1989. Design and construction of a quarter scale model of the walking beam. Martin Marietta Space Systems. Denver. Dickmanns, E., and Mysliwetz, B. 1992. Recursive 3-d road and relative ego-state recognition. IEEE Trans. Pattern Anal. Machine Intell. 14(2):199-213. Gat, E. 1992. Integrating planning and reacting in a heterogeneous asynchronous architecture for controlling real-world mobile robots. Proc. Nat. Conf. Artificial Intelligence, San Jose, CA, pp. 809-815.

Krotkov, E., Simmons, R., and Thorpe, C. 1990. Single-

Gat, E., Desai, R., Ivlev, R., Loch, J., and Miller, D.

planetary
from

1994. Behavior control for robotic exploration of surfaces. IEEE Trans. Robot. Automation
measurements

10(4):490-503.
Hebert, M., and Krotkov, E. 1992. 3-d

leg walking with integrated perception, planning, and control. Proc. IEEE Int. Workshop on Intelligent Robots and Systems, Tsuchiura, Japan, pp. 97102. Kweon, I. S., and Kanade, T. 1992. High-resolution terrain map from multiple sensor data. IEEE Trans. Pattern Anal. Machine Intell. 14(2):278-292. Mahalingam, S., and Whittaker, W. 1989. Terrain adaptive gaits for walkers with completely overlapping leg workspaces. Proc. Robots 13, Gaithersburg, MD, pp. 1-14. Matthies, L. 1989. Dynamic Stereo Vision. PhD thesis, Carnegie Mellon University. Also available as Technical report CMU-CS-89-195. Matthies, L. 1992. Stereo vision for planetary rovers: Stochastic modeling to near real-time implementation. Int. J. Computer Vision 8(1):71-91. Office of Technology Assessment. 1991. Exploring the Moon and Mars: Choices for the Nation. OTA-ISC502. Washington, DC: U.S. Government Printing Office. Pfeiffer, F., Weidermann, H. J., and Danowski, P. 1991. Dynamics of the walking stick insect. IEEE Control
Sys. 11(2):9-13. Proy, C., Hotz, B., Faugeras, O., Gernesson, P., and
Berhod, M. I993. Onboard vision system for
bile
a mo-

good are they? Int. J. Image Vision Computing 10(3):170-178. Hirose, S. 1984. A study of design and control of a quadruped walking vehicle. Int. J. Robot. Res. 3(2):113-133. Hirose, S., and Ootsukasa, N. 1993. Design and development of a quadra-rhomb rover for mars explo-

imaging

laser radars: How

planetary exploration robot. Proc. Workshop on Computer Vision for Space Applications, Antibes,
France, pp. 2-12. Raibert, M. 1986. Legged Robots That Balance. Cam-

bridge,

MA: MIT Press.

179
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015

Roston, G., and Krotkov, E. Dead reckoning navigation

Stone, H. 1993. Design and control of the

mesur/path-

six-legged walking robot. Proc: IEEE Int. Workshop on Intelligent Robots and Systems, Raleigh, NC, pp.607-612.
for
a

Rumelhart, D., Hinton, G., and Williams, R. 1988. Learn-

ing internal representations by error propagation. In Rumelhart, D., and McClelland, J. (eds.): Parallel Distributed Processing. Vol. 1: Foundations. Cambridge,
MA: MIT Press, pp. 318-362. Russell, K. 1983. Odex i: The first functionoid. Robot.

Age 5(5):12-18.
Simmons, R. 1992. Monitoring and
autonomous
error

recovery for

walking. Workshop on Intelliand 1407-1412. Robots Systems, pp. gent Simmons, R. 1990. An architecture for coordinating planning, sensing, and action. Proc. of DARPA Workshop on Innovative Approaches to Planning, Scheduling and Control, San Diego, CA, pp. 292-297. Simmons, R. 1994. Structured control for autonomous robots. IEEE Trans. Robot. Automation 10(1):34-43. Song, S., and Waldron, K., 1989. Machines That Walk: The Adaptive Suspension Vehicle. Cambridge, MA:
Proc. IEEE

finder microrover. Proc. Int. Conf. Advanced Robotics, Tokyo, Japan, pp. 263-270. Thorpe, C. (ed.). 1990. Vision and Navigation: The Carnegie Mellon Navlab. Boston: Kluwer Academic Publishers. Turk, M. A., Morgenthaler, D. G., Gramban, K. D., and Marra, M. 1988. Vits&mdash;a vision system for autonomous land vehicle navigation. PAMI 10(3). Wettergreen, D., Thomas, H., and Thorpe, C. 1990. Planning strategies for the ambler walking robot. Proc. IEEE Intl. Conf. Systems Engineering. Wilcox, B., and Gennery, D. 1987. A Mars rover for the 1990’s. J. Br Interplanet. Soc. 40:484-488.

Wilcox, B., Matthies, L., Gennery, D., Cooper, B., Nguyen, T., Litwin, T., Mishkin, A., and Stone,
H. 1992. Robotic vehicles for planetary exploration. Proc. IEEE Int. Conf. Robotics and Automation. Nice,

France, pp. 175-180.

MIT Press.

180
Downloaded from ijr.sagepub.com at Shanghai Jiaotong University on August 30, 2015


相关文章:
The GraphSLAM Algorithm With Applications to Large-....pdf
The International Journal of Robotics Research http://ijr.sagepub.com/ The ...lter perspective is also related to early work by Bulata and Devy (1996)...
SCI杂志中科院分区表(完整版).xls
INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH ...155 156 157 158 159 160 161 0969-0239 0017-...1996-1944 1842-3582 0965-0393 1063-8016 1570-...
Journal Review - The International Journal of Robotics Research.unkown
Journal Review - The International Journal of Robotics Research September, 2012 Distributed robotic sensor networks: An information-theoretic approach Vol. 31 ...
(Submitted to The International Journal of Robotics Research,....unkown
(Submitted to The International Journal of Robotics Research, May 1986) A ...di Informatica e Sistemistica Via Claudio 21, 80125 Napoli, Italy Wayne J...
proach. The International Journal of Robotics Research, Vol 6....unkown
The International Journal of Robotics Research, Vol 6(10):pp. 628{649, ...80 70 Total planning time Precedence graphs construction time 60 LPLAN time...
...:TheInternationalJournalofRobotics....unkown
● fundamentaldifferencesbetweentypicalcomputervisiontasksandroboticvision ● deeplearningforperception,...
..." The International Journal of Robotics Research, 32(8).unkown
IFAC TC for evaluation: 1.3 Discrete-event and hybrid systems Description of the topic: Research in multi-robot control systems has been traditionally ...
...Problem', International Journal of Robotics Research, V.unkown
International Journal of Robotics Research, Vol. ...8, No. 6, pp.80-96. Angeles, J., 1985, ...Corke, P.I., 1996, 'A Robotics Toolbox for ...
references.pdf
International Journal of Robotics Research 10, 628...Cutkosky (1996, December). Practical force-motion...P. Krotkov, and M. T. Mason (1995). ...
Bibliography.pdf
Robotics Research, vol. 5, no. 3, pp. 27-...Krotkov. Experimental Characterization of the ...[80] H. Y. Shum, K. Ikeuchi and R. Reddy...
and theory logic, psychology and artificial intelligence ....pdf
in International Journal of Robotics Research, ...Krotkov, W. Whittaker, B. Albrecht, J. Bares,... in Unstructured Terrain,” US$80,000, 1996. ...
2014年最新SCI分区情况(JCR)_图文.xls
INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH ...155 156 157 158 159 160 1932-4529 1383-5866 ...1996-1944 1842-3582 0965-0393 1063-8016 1570-...
THE INTERNATIONAL JOURNAL OF MEDICAL ROBOTICS AND C....pdf
THE INTERNATIONAL JOURNAL OF MEDICAL ROBOTICS AND COMPUTER ASSISTED SURGERY Int J Med Robotics Comput Assist Surg 2006; 2: 123138. Published online in...
顶级期刊排名.doc
16 Publications AI - Artificial Intelligence JAIR - Journal of Artificial Intelligence Research IJRR - International Journal of Robotic Research AIM - AI ...
Intelligence tests for robots: Solving perceptual reasoning ....unkown
Intelligence tests for robots: Solving perceptual reasoning tasks with a humanoid robot by Connor Schenck A thesis submitted to the graduate faculty in ...
International Journal of Robotics Research, Vol. 20, No. 8, p....unkown
International Journal of Robotics Research, Vol. 20, No. 8, p. 635659, 2001 ¤ § ¨¤ ...
International Journal of Robotics Research.unkown
International Journal of Robotics Research Information Surfing for Radiation Map Building Journal: The International Journal of Robotics Research Manuscript ID: ...
...Steering. International Journal of Robotics Research, 25(5....unkown
Specific research interests lie in compu
...and Robots. International Journal of Robotics Research, 24....unkown
The International Journal of Robotics Research, 18(7):621 649, July ...Biometrika, 83(1):8194, 1996. [17] H. Chan and A. Perrig. ACE:...
INTERNATIONAL JOURNAL OF RESEARCH IN COMPUTER APPLICATIONS ....unkown
INTERNATIONAL JOURNAL OF RESEARCH IN COMPUTER APPLICATIONS AND ROBOTICS Vol.1 Issue.9, Pg.: 176-183 December 2013 INTERNATIONAL JOURNAL OF RESEARCH IN ...
更多相关标签: