Perceptive whole‐body planning for multilegged robots in confined spaces

Legged robots are exceedingly versatile and have the potential to navigate complex, confined spaces due to their many degrees of freedom. As a result of the computational complexity, there exist no online planners for perceptive whole‐body locomotion of robots in tight spaces. In this paper, we present a new method for perceptive planning for multilegged robots, which generates body poses, footholds, and swing trajectories for collision avoidance. Measurements from an onboard depth camera are used to create a three‐dimensional map of the terrain around the robot. We randomly sample body poses then smooth the resulting trajectory while satisfying several constraints, such as robot kinematics and collision avoidance. Footholds and swing trajectories are computed based on the terrain, and the robot body pose is optimized to ensure stable locomotion while not colliding with the environment. Our method is designed to run online on a real robot and generate trajectories several meters long. We first tested our algorithm in several simulations with varied confined spaces using the quadrupedal robot ANYmal. We also simulated experiments with the hexapod robot Weaver to demonstrate applicability to different legged robot configurations. Then, we demonstrated our whole‐body planner in several online experiments both indoors and in realistic scenarios at an emergency rescue training facility. ANYmal, which has a nominal standing height of 80 cm and a width of 59 cm, navigated through several representative disaster areas with openings as small as 60 cm. Three‐meter trajectories were replanned with 500 ms update times.     

Configuration representation and reconfiguration optimization for the reconfigurable robots with independent manipulation

Single module of the reconfigurable robots with independent manipulation can perform the actions of locomotion and manipulation. In conformity with the request for achieving autonomous operation in the unstructurized environment instead of fixed operation in the structurized environment, these robots are applied in the complicated and dangerous environment. The existing researches on the configuration theory focus on the reconfigurable robots with limited locomotion and the ones with independent locomotion, not being applicable to the reconfigurable robots with independent manipulation. The vector configuration is put forward, the research content of which contains the topology and locomotion direction of configuration, the posture and orientation and connection relation between modules. Module state vector and configuration state matrix are proposed for representation methodology for the swarm configuration of these reconfigurable robots, which supports transformation operation to represent and trigger behavior motion of the module and reconfiguration between configurations. Optimization algorithm of assembly reconfiguration applying workload as the optimization target is presented, as well as optimization algorithm of transformation reconfiguration applying the integration of posture orientation workload and connection workload. The result of optimization is the relation of state transformation between the initial configuration and the object one as the basic of reconfiguration plan and control. Supported by the National High-Tech Research and Development Program of China (Grant No. 2006AA04Z254) and the Scientific Research Fund for Doctor of Liaoning Provice (Grant No. 20071007)     

Narrow passage sampling for probabilistic roadmap planning

Probabilistic roadmap (PRM) planners have been successful in path planning of robots with many degrees of freedom, but sampling narrow passages in a robot's configuration space remains a challenge for PRM planners. This paper presents a hybrid sampling strategy in the PRM framework for finding paths through narrow passages. A key ingredient of the new strategy is the bridge test, which reduces sample density in many unimportant parts of a configuration space, resulting in increased sample density in narrow passages. The bridge test can be implemented efficiently in high-dimensional configuration spaces using only simple tests of local geometry. The strengths of the bridge test and uniform sampling complement each other naturally. The two sampling strategies are combined to construct the hybrid sampling strategy for our planner. We implemented the planner and tested it on rigid and articulated robots in 2-D and 3-D environments. Experiments show that the hybrid sampling strategy enables relatively small roadmaps to reliably capture the connectivity of configuration spaces with difficult narrow passages.     

Multi‐AUV motion planning for archeological site mapping and photogrammetric reconstruction

This paper presents coupled and decoupled multi‐autonomous underwater vehicle (AUV) motion planning approaches for maximizing information gain. The work is motivated by applications in which multiple AUVs are tasked with obtaining video footage for the photogrammetric reconstruction of underwater archeological sites. Each AUV is equipped with a video camera and side‐scan sonar. The side‐scan sonar is used to initially collect low‐resolution data to construct an information map of the site. Coupled and decoupled motion planning approaches with respect to this map are presented. Both planning methods seek to generate multi‐AUV trajectories that capture close‐up video footage of a site from a variety of different viewpoints, building on prior work in single‐AUV rapidly exploring random tree (RRT) motion planning. The coupled and decoupled planners are compared in simulation. In addition, the multiple AUV trajectories constructed by each planner were executed at archeological sites located off the coast of Malta, albeit by a single‐AUV due to limited resources. Specifically, each AUV trajectory for a plan was executed in sequence instead of simultaneously. Modifications are also made by both planners to a baseline RRT algorithm. The results of the paper present a number of trade‐offs between the two planning approaches and demonstrate a large improvement in map coverage efficiency and runtime.     

On the predictability of domain‐independent temporal planners

Temporal planning is a research discipline that addresses the problem of generating a totally or a partially ordered sequence of actions that transform the environment from some initial state to a desired goal state, while taking into account time constraints and actions' duration. For its ability to describe and address temporal constraints, temporal planning is of critical importance for a wide range of real‐world applications. Predicting the performance of temporal planners can lead to significant improvements in the area, as planners can then be combined in order to boost the performance on a given set of problem instances. This paper investigates the predictability of the state‐of‐the‐art temporal planners by introducing a new set of temporal‐specific features and exploiting them for generating classification and regression empirical performance models (EPMs) of considered planners. EPMs are also tested with regard to their ability to select the most promising planner for efficiently solving a given temporal planning problem. Our extensive empirical analysis indicates that the introduced set of features allows to generate EPMs that can effectively perform algorithm selection, and the use of EPMs is therefore a promising direction for improving the state of the art of temporal planning, hence fostering the use of planning in real‐world applications.     

ModRED: Hardware design and reconfiguration planning for a high dexterity modular self-reconfigurable robot for extra-terrestrial exploration

This paper presents a homogeneous modular robot system design based on four per-module degrees of freedom (DOF), including a prismatic DOF to increase the versatility of its reconfiguration and locomotion capabilities. The ModRED (Modular Robot for Exploration and Discovery) modules are developed with rotary-plate genderless single sided docking mechanisms (RoGenSiD) that allow chain-type configurations and lead towards hybrid-type configurations. Various locomotion gaits are simulated through the Webots robot simulator and implemented in the real ModRED system. This work also addresses the problem of dynamic reconfiguration in a modular self-reconfigurable robot (MSR). The self-reconfiguration problem is modeled as an instance of the graph-based coalition formation problem. We formulate the problem as a linear program that finds the “best” partition or coalition structure among a set of ModRED modules. The technique is verified experimentally for a variety of settings on an accurately simulated model of the ModRED robot within the Webots robot simulator. Our experimental results show that our technique can find the best partition with a reasonably low computational overhead.     

The corridor map method: a general framework for real‐time high‐quality path planning

In many virtual environment applications, paths have to be planned for characters to traverse from a start to a goal position in the virtual world while avoiding obstacles. Contemporary applications require a path planner that is fast (to ensure real‐time interaction with the environment) and flexible (to avoid local hazards such as small and dynamic obstacles). In addition, paths need to be smooth and short to ensure natural looking motions. Current path planning techniques do not obey these criteria simultaneously. For example, A* approaches generate unnatural looking paths, potential field‐based methods are too slow, and sampling‐based path planning techniques are inflexible. We propose a new technique, the Corridor Map Method (CMM), which satisfies all the criteria. In an off‐line construction phase, the CMM creates a system of collision‐free corridors for the static obstacles in an environment. In the query phase, paths can be planned inside the corridors for different types of characters while avoiding dynamic obstacles. Experiments show that high‐quality paths for single characters or groups of characters can be obtained in real‐time. Copyright © 2007 John Wiley & Sons, Ltd.     

Weaver: Hexapod robot for autonomous navigation on unstructured terrain

Legged robots are an efficient alternative for navigation in challenging terrain. In this paper we describe Weaver, a six‐legged robot that is designed to perform autonomous navigation in unstructured terrain. It uses stereo vision and proprioceptive sensing based terrain perception for adaptive control while using visual‐inertial odometry for autonomous waypoint‐based navigation. Terrain perception generates a minimal representation of the traversed environment in terms of roughness and step height. This reduces the complexity of the terrain model significantly, enabling the robot to feed back information about the environment into its controller. Furthermore, we combine exteroceptive and proprioceptive sensing to enhance the terrain perception capabilities, especially in situations in which the stereo camera is not able to generate an accurate representation of the environment. The adaptation approach described also exploits the unique properties of legged robots by adapting the virtual stiffness, stride frequency, and stride height. Weaver's unique leg design with five joints per leg improves locomotion on high gradient slopes, and this novel configuration is further analyzed. Using these approaches, we present an experimental evaluation of this fully self‐contained hexapod performing autonomous navigation on a multiterrain testbed and in outdoor terrain.     

Design of Statically Stable Walking Robot: A Review

The superior mobility characteristics of legged animals compared to those of wheeled or tracked vehicles for off‐road locomotion motivated the development of artificial walking machines. The sustained worldwide efforts for the last few decades resulted in a large number of legged robots with different levels of sophistication. Here, various design approaches made so far to realize artificial legged locomotion are discussed. Mainly, different vehicle configurations as well as leg mechanisms which are already explored by researchers are reviewed in brief. The author hopes that this will serve as a brief account of previous research efforts and help future walking robot designers to develop more sophisticated machines. © 2003 Wiley Periodicals, Inc.     

Risk‐aware Path Planning for Autonomous Underwater Vehicles using Predictive Ocean Models

Recent advances in Autonomous Underwater Vehicle (AUV) technology have facilitated the collection of oceanographic data at a fraction of the cost of ship‐based sampling methods. Unlike oceanographic data collection in the deep ocean, operation of AUVs in coastal regions exposes them to the risk of collision with ships and land. Such concerns are particularly prominent for slow‐moving AUVs since ocean current magnitudes are often strong enough to alter the planned path significantly. Prior work using predictive ocean currents relies upon deterministic outcomes, which do not account for the uncertainty in the ocean current predictions themselves. To improve the safety and reliability of AUV operation in coastal regions, we introduce two stochastic planners: (a) a Minimum Expected Risk planner and (b) a risk‐aware Markov Decision Process, both of which have the ability to utilize ocean current predictions probabilistically. We report results from extensive simulation studies in realistic ocean current fields obtained from widely used regional ocean models. Our simulations show that the proposed planners have lower collision risk than state‐of‐the‐art methods. We present additional results from field experiments where ocean current predictions were used to plan the paths of two Slocum gliders. Field trials indicate the practical usefulness of our techniques over long‐term deployments, showing them to be ideal for AUV operations.     

Global and regional path planners for integrated planning and navigation

This paper presents a hierarchical strategy for field mobile robots that incorporates path planning at different ranges. At the top layer is a global path planner that utilizes gross terrain characteristics, such as hills and valleys, to determine globally safe paths through the rough terrain. This information is then passed via waypoints to a regional layer that plans appropriate navigation paths using regional terrain characteristics. The global and regional path planners share the same map information, but at different ranges. The motion recommendations from the regional layer are then combined with those of the reactive navigation layer to provide reactive control for the mobile robot. Details of the global and regional path planners are discussed, and simulation and experimental results are presented. © 2005 Wiley Periodicals, Inc.     

WALK‐MAN: A High‐Performance Humanoid Platform for Realistic Environments

In this work, we present WALK‐MAN, a humanoid platform that has been developed to operate in realistic unstructured environment, and demonstrate new skills including powerful manipulation, robust balanced locomotion, high‐strength capabilities, and physical sturdiness. To enable these capabilities, WALK‐MAN design and actuation are based on the most recent advancements of series elastic actuator drives with unique performance features that differentiate the robot from previous state‐of‐the‐art compliant actuated robots. Physical interaction performance is benefited by both active and passive adaptation, thanks to WALK‐MAN actuation that combines customized high‐performance modules with tuned torque/velocity curves and transmission elasticity for high‐speed adaptation response and motion reactions to disturbances. WALK‐MAN design also includes innovative design optimization features that consider the selection of kinematic structure and the placement of the actuators with the body structure to maximize the robot performance. Physical robustness is ensured with the integration of elastic transmission, proprioceptive sensing, and control. The WALK‐MAN hardware was designed and built in 11 months, and the prototype of the robot was ready four months before DARPA Robotics Challenge (DRC) Finals. The motion generation of WALK‐MAN is based on the unified motion‐generation framework of whole‐body locomotion and manipulation (termed loco‐manipulation). WALK‐MAN is able to execute simple loco‐manipulation behaviors synthesized by combining different primitives defining the behavior of the center of gravity, the motion of the hands, legs, and head, the body attitude and posture, and the constrained body parts such as joint limits and contacts. The motion‐generation framework including the specific motion modules and software architecture is discussed in detail. A rich perception system allows the robot to perceive and generate 3D representations of the environment as well as detect contacts and sense physical interaction force and moments. The operator station that pilots use to control the robot provides a rich pilot interface with different control modes and a number of teleoperated or semiautonomous command features. The capability of the robot and the performance of the individual motion control and perception modules were validated during the DRC in which the robot was able to demonstrate exceptional physical resilience and execute some of the tasks during the competition.     

Optimisation based path planning for car parking in narrow environments

In the last decades, a large variety of robot motion planners emerged. However, manoeuvring in very narrow environments, e.g., for common parking scenarios, cannot be reliably handled with existing path planners at low computing costs. This is why, this paper presents a fast optimisation based path planner which specialises on narrow environments. In the proposed approach, the kinematic differential equations are discretised. For the resulting discrete path segments, a static optimisation problem is formulated to determine the path independently of the considered scenario. In each iteration step, the path length is also optimised to handle close distances to the obstacles as well as longer driving distances. Due to the local nature heuristic rules for driving direction changes are formulated which intend to imitate the behaviour of a human driver. The drawback of the local nature is the lack of global information to handle scenarios with obstacles blocking the path. To overcome this problem, a tree-based guidance for the local planner is introduced. The landmarks for the tree are implicitly created by the local planner allowing an efficient exploration of the free configuration space. The performance of the algorithm is evaluated utilising Monte-Carlo simulations and compared to state-of-the-art path planning algorithms.     

Projective Blue‐Noise Sampling

We propose projective blue‐noise patterns that retain their blue‐noise characteristics when undergoing one or multiple projections onto lower dimensional subspaces. These patterns are produced by extending existing methods, such as dart throwing and Lloyd relaxation, and have a range of applications. For numerical integration, our patterns often outperform state‐of‐the‐art stochastic and low‐discrepancy patterns, which have been specifically designed only for this purpose. For image reconstruction, our method outperforms traditional blue‐noise sampling when the variation in the signal is concentrated along one dimension. Finally, we use our patterns to distribute primitives uniformly in 3D space such that their 2D projections retain a blue‐noise distribution.     

Planning of collision-free paths for a reconfigurable dual manipulator equipped mobile robot

In this paper, we study the problem of finding a collision-free path for a mobile robot which possesses manipulators. The task of the robot is to carry a polygonal object from a starting point to a destination point in a possibly culttered environment. In most of the existing research on robot path planning, a mobile robot is approximated by a fixed shape, i.e., a circle or a polygon. In our task planner, the robot is allowed to change configurations for avoiding collision. This path planner operates using two algorithms: the collision-free feasible configuration finding algorithm and the collision-free path finding algorithm. The collision-free feasible configuration finding algorithm finds all collision-free feasible configurations for the robot when the position of the carried object is given. The collision-free path finding algorithm generates some candidate paths first and then uses a graph search method to find a collision-free path from all the collision-free feasible configurations along the candidate paths. The proposed algorithms can deal with a cluttered environment and is guaranteed to find a solution if one exists.     

Autonomous Driving with Concurrent Goals and Multiple Vehicles: Mission Planning and Architecture

We introduce a new distributed planning paradigm, which permits optimal execution and dynamic replanning of complex multi-goal missions. In particular, the approach permits dynamic allocation of goals to vehicles based on the current environment model while maintaining information-optimal route planning for each individual vehicle to individual goals. Complex missions can be specified by using a grammar in which ordering of goals, priorities, and multiple alternatives can be described. We show that the system is able to plan local paths in obstacle fields based on sensor data, to plan and update global paths to goals based on frequent obstacle map updates, and to modify mission execution, e.g., the assignment and ordering of the goals, based on the updated paths to the goals.The multi-vehicle planning system is based on the GRAMMPS planner; the on-board dynamic route planner is based on the D* planner. Experiments were conducted with stereo and high-speed ladar as the to sensors used for obstacle detection. This paper focuses on the multi-vehicle planner and the systems architecture. A companion paper (Brumitt et al., 2001) analyzes experiments with the multi-vehicle system and describes in details the other components of the system.     

Terrain-evaluation-based motion planning for legged locomotion on irregular terrain

The path planning of legged locomotion is complex in that path generation is based on constraints not only from body motion, but also from leg motion. A general approach to path planning will fail in generating a feasible path for walking machines when facing the huge searching space of legged locomotion. In this paper, an effective method of path planning is introduced by virtue of terrain evaluation. It maps obstacles into the robot configuration space by evaluating the obstacles' influence on the legged locomotion. The evaluation produces an index of terrain, called terrain complexity, for path planning. Using potential-guided searching, the terrain with mapped obstacles is searched to generate a feasible path.     

Planar legged walking of a passive-spine hexapod robot

This paper proposes a new legged walking method for a novel passive-spine hexapod robot. This robot consists of several body segments connected by passive body joints. Each of the body segments carries two 1-DoF (degree of freedom) actuated legs. The robot is capable of achieving planar legged walking by rapidly abducting and adducting its legs. To model the mobility of a robot based on this simple design, the candidate configurations from all possible configurations are first selected in a mobility analysis of the robot based on the screw theory. All the feasible sequences of these candidate configurations are then searched to form planar locomotion gaits. Next, locomotive performance of the gaits is analyzed. Finally, the proposed locomotion design and gait planning methods are verified through simulations and experiments.     

A configuration deactivation algorithm for boosting probabilistic roadmap planning of robots

We present a method to improve the execution time used to build the roadmap in probabilistic roadmap planners. Our method intelligently deactivates some of the configurations during the learning phase and allows the planner to concentrate on those configurations that are most likely going to be useful when building the roadmap. The method can be used with many of the existing sampling algorithms. We ran tests with four simulated robot problems typical in robotics literature. The sampling methods applied were purely random, using Halton numbers, Gaussian distribution, and bridge test technique. In our tests, the deactivation method clearly improved the execution times. Compared with pure random selections, the deactivation method also significantly decreased the size of the roadmap, which is a useful property to simplify roadmap planning tasks.     

Optimization and evaluation of swing leg retraction for a hydraulic biped robot

To improve the locomotion performance of legged robots, the swing leg retraction (SLR) technique is investigated in a hydraulic biped robot. First, the influence of SLR on the locomotion performance of the hydraulic biped robot is analyzed in theory and simulations based on an extended spring load inverted pendulum model. The influence contains three performance indicators: energy loss/effiency, friction/slipping, and impact/compliance. Second, by synthesizing three performance indicators, using unified objective method and particle swarm optimization algorithm, the optimal SLR rate for gait planning based on Bezier curve is addressed. Finally, experiments are implemented to validate the effectiveness and feasibility of proposed method. And, the results show that the SLR technique is useful to reduce the impact force, improve the robot's locomotion stability and make room for impedance performance improvement of compliance controller. This research provides an insight for locomotion control of hydraulic legged robots.