View planning for exploration via maximal C-space entropy reduction for robot mounted range sensors

We introduced the concept of C-space entropy recently as a measure of knowledge of configuration space (C-space) for sensor-based exploration and path planning for general robot–sensor systems. The robot plans the next sensing action to maximally reduce the expected C-space entropy, also called the Maximal expected Entropy Reduction (MER) criterion. The resulting view planning algorithms showed significant improvement of exploration rate over physical space-based criteria. However, this expected C-space entropy computation made two idealized assumptions: (i) that the sensor field of view (FOV) is a point and (ii) that there are no occlusion (or visibility) constraints, i.e., as if the sensor can sense through the obstacles. We extend the expected C-space entropy formulation where these two assumptions are relaxed, and consider a range sensor with non-zero volume FOV and occlusion constraints, thereby modeling a realistic range sensor. Planar simulations and experimental results on the SFU Eye-in-Hand system show that the new formulation results in further improvement in C-space exploration efficiency over the point FOV sensor-based MER formulation.     

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.     

Implementation of omnidirectional crawl for a quadruped robot

As a reptile animal crawls in a cluttered environment, so a quadruped robot should be able to crawl on an irregular ground profile with its static stability by adopting the straightgoing and standstill-turning free gaits. The generalized and explicit formulations for the automatic generation of straight-going gaits and various standstill-turning gaits are presented in this paper. The maximized stride for the straight-going gait and the maximum turning angle for the turning gait of a quadruped robot named TITAN-VIII in a gait cycle are discussed by considering the robot's mechanism constraints and the irregularities of the ground profile. The control algorithm, including control of the joint positions of the robot, is described to implement the desired walking path of the quadruped robot. The effectiveness of the proposed method is demonstrated through experimental result.     

Non-holonomic Path Planning of a Free-Floating Space Robotic System Using Genetic Algorithms

In this paper, the non-holonomic characteristic of a free-floating space robotic system is used to plan the path of the manipulator joints, by whose motion the base attitude and the manipulator joints attain the desired states. Here, we parameterize the joint trajectory using sinusoidal functions, whose arguments are high-order polynomials. Then, we define the cost function for optimization according to the constraint conditions and the accuracy of the space robot. Finally, genetic algorithms (GAs) are used to search for the solutions of the parameters. Compared with others, our approach has advantages as follows. (i) The motion of the manipulator and the disturbance on the base are practically constrained. (ii) The dynamic singularities cannot affect the algorithm since only the direct kinematic equations are utilized. (iii) The planned path is smooth and more applicable for the control of the manipulator. (iv) The convergence of the algorithm is not affected by the attitude singularity since the orientation error is represented by quaternion, which is globally singularity-free. The simulation results of the spacecraft with a 6-d.o.f. manipulator verify the performance and the validity of the proposed method.     

Study on Non-holonomic Cartesian Path Planning of a Free-Floating Space Robotic System

The non-holonomic characteristic of a free-floating space robotic system is used to plan the path of the manipulator joints, by whose motion the base attitude and the inertial pose (the position and orientation with respect to the inertial frame) of the end-effector attain the desired values. First, the kinematic equations of a free-floating space robot are simplified and the system state variables are transformed to another form composed of base attitude and joint angles. Then, the joint trajectories are parameterized using sinusoidal functions, whose arguments are seven-order polynomials. Third, the planning problem is transformed to an optimization problem; the cost function, defined according to the accuracy requirements of system variables, is the function of the parameters to be determined. Finally, the Particle Swarm Optimization (PSO) algorithm is used to search the solutions of the parameters that determine the joint trajectories. The presented method meets three typical applications: (i) point-to-point maneuver of the end-effector without changing the base attitude, (ii) attitude maneuver of the base without changing the end-effector's pose and (iii) point-to-point maneuver of the end-effector with adjusting the base attitude synchronously. The simulation results of a spacecraft with a 6-d.o.f. manipulator verify the performance and the validity of the proposed method.     

Genetic Programming-Based Automatic Gait Generation in Joint Space for a Quadruped Robot

This paper introduces a new approach to developing a fast gait for a quadruped robot using genetic programming (GP). Planning gaits for legged robots is a challenging task that requires optimizing parameters in a highly irregular and multi-dimensional space. Several recent approaches have focused on using genetic algorithms (GAs) to generate gaits automatically and have shown significant improvement over previous gait optimization results. Most current GA-based approaches optimize only a small, pre-selected set of parameters, but it is difficult to decide which parameters should be included in the optimization to get the best results. Moreover, the number of pre-selected parameters is at least 10, so it can be relatively difficult to optimize them, given their high degree of interdependence. To overcome these problems of the typical GA-based approach, we have proposed a seemingly more efficient approach that optimizes joint trajectories instead of locus-related parameters in Cartesian space, using GP. Our GP-based method has obtained much-improved results over the GA-based approaches tested in experiments on the Sony AIBO ERS-7 in the Webots environment. The elite archive mechanism is introduced to combat the premature convergence problems in GP and has shown better results than a traditional multi-population approach.     

Development of a steerable,wheel-type,in-pipe robot and its path planning

This paper presents the development of a steerable, wheel-type, in-pipe robot and its path planning. First, we show the construction of the robot and demonstrate its locomotion inside a pipe. The robot is composed of two wheel frames and an extendable arm which links the centers of the two wheel frames. The arm presses the frames against the interior wall of a pipe to support the robot. The wheels of the frames are steered independently so that the robot can turn within a small radius of rotation. Experimental results of the locomotion show that the steering control is effective for autonomous navigation to avoid obstacles and to enter the joint spaces of L- and T-shaped pipes. Generally, autonomous navigation is difficult for wheel-type robots because the steering angles required to travel along a desired path are not easily determined. In our previous work, the relationship between the steering angles and locomotion trajectories in a pipe has already been analyzed. Using this analysis, we propose the path planning in pipes.     

Dynamic turning control of a quadruped locomotion robot using oscillators

We propose a dynamic turning control system for a quadruped robot that uses non-linear oscillators. It is composed of a spontaneous locomotion controller and voluntary motion controller. We verified the mechanical capabilities of the dynamic turning motion of the proposed control system through numerical simulations and hardware experiments. Various turning speeds and orientations made the motion of the robot asymmetrical in terms of the duty ratio, stride and center of pressure. The proposed controller actively and adaptively controlled redundant degrees of freedom to cancel out dynamic asymmetry, and established stable turning motion at various locomotion speeds and turning orientations.     

Adaptive dynamic walking of a quadruped robot using a neural system model

We are trying to induce a quadruped robot to walk dynamically on irregular terrain by using a neural system model. In this paper, we integrate several reflexes, such as a stretch reflex, a vestibulospinal reflex and extensor/flexor reflexes, into a central pattern generator (CPG). We try to realize adaptive walking up and down a slope of 12°, walking over an obstacle 3 cm in height, and walking on terrain undulation consisting of bumps 3 cm in height with fixed parameters of CPGs and reflexes. The success in walking on such irregular terrain in spite of stumbling and landing on obstacles shows that the control method using a neural system model proposed in this study has the ability for autonomous adaptation to unknown irregular terrain. In order to clarify the role of a CPG, we investigate the relation between parameters of a CPG and the mechanical system by simulations and experiments. CPGs can generate stable walking suitable for the mechanical system by receiving inhibitory input as sensory feedback and generate adaptive walking on irregular terrain by receiving excitatory input as sensory feedback. MPEG footage of these experiments can be seen at: http://www.kimura.is.uec.ac.jp.     

Local path planning using a new artificial potential function composition and its analytical design guidelines

This paper presents a new framework for path planning based on artificial potential functions (APFs). In this scheme, the APFs for path planning have a multiplicative and additive composition between APFs for goal destination and APFs for obstacle avoidance, unlike conventional composition where the APF for obstacle avoidance is added to the APF for goal destination. In particular, this paper presents a set of analytical guidelines for designing potential functions to avoid local minima for a number of representative scenarios based on the proposed framework for path planning. Specifically the following cases are addressed: (i) a non-reachable goal problem (a case in which the potential of the goal is overwhelmed by the potential of an obstacle), (ii) an obstacle collision problem (a case in which the potential of the obstacle is overwhelmed by the potential of the goal) and (iii) a narrow passage problem (a case in which the potential of the goal is overwhelmed by the potential of two obstacles). The example results for each case show that the proposed scheme can effectively construct a path-planning system with the capability of reaching a goal and avoiding obstacles despite possible local minima.     

Terrain evaluation and its application to path planning for walking machines

Motion planning of walking machines normally contains two aspects: gait planning and body trajectory planning. When generating an optimal body trajectory on natural terrain, the leg movement must be taken into account. Due to the large searching space resulting from the combination of leg movement and terrain conditions, it is quite time consuming to produce an optimal result of body trajectory planning. In this paper, an effective method of body trajectory planning is introduced by virtue of a terrain evaluation that links the terrain conditions with machine mobility. Based on the evaluation, a potential field is constructed for graph searching. Best first planning (BFP) is adopted to search the optimal path. The path generated with the proposed method could offer the best opportunity to place the machine feet moving with a certain gait over a rough terrain. The assumptions and shortages associated with the present work are also discussed.     

Motion Planning Strategy for Finding an Object with a Mobile Manipulator in Three-Dimensional Environments

In this paper, we investigate the problem of minimizing the average time required to find an object in a known three-dimensional environment. We consider a 7-d.o.f. mobile manipulator with an 'eye-in-hand' sensor. In particular, we address the problem of searching for an object whose unknown location is characterized by a known probability density function. We present a discrete formulation, in which we use a visibility-based decomposition of the environment. We introduce a sample-based convex cover to estimate the size and shape of visibility regions in three dimensions. The resulting convex regions are exploited to generate trajectories that make a compromise between moving the manipulator base and moving the robotic arm. We also propose a practical method to approximate the visibility region in three dimensions of a sensor limited in both range and field of view. The quality and success of the generated paths depend significantly on the sensing robot capabilities. In this paper, we generate searching plans for a mobile manipulator equipped with a sensor limited in both field of view and range. We have implemented the algorithm and present simulation results.     

New repulsive potential functions with angle distributions for local path planning

This paper presents new repulsive potential functions (RPFs) for point robot path planning. In this scheme, the RPF for path planning has a different magnitude at each direction of a RPF based on the angle between a goal and an obstacle, unlike a conventional RPF in which the same magnitude at each direction is obtained. In doing so, the RPF attempts to overcome some of the typical problems that may arise with the conventional RPF. In particular, this paper presents a set of analyses for designing potential functions to avoid local minima for a number of representative scenarios. Specifically, the following cases are addressed: (i) a non-reachable goal problem (a case in which the potential of the goal is overwhelmed by the potential of an obstacle), (ii) an obstacle collision problem (a case in which the potential of the obstacle is overwhelmed by the potential of the goal) and (iii) a narrow passage problem (a case in which the potential of the goal is overwhelmed by the potential of two obstacles). The proposed RPF scheme eliminates the non-feasible area for the three cases by the help of an angle-varying magnitude between a goal and an obstacle. The example results show that the proposed RPF scheme can effectively construct a path-planning system with the capability of reaching a goal and avoiding obstacles despite possible local minima.     

Triple RRTs: An Effective Method for Path Planning in Narrow Passages

Although Rapidly-exploring Random Trees (RRTs) have been successfully applied in path planning of robots with many degrees of freedom under non-holonomic and differential constraints, rapidly identifying and passing through narrow passages in a robot's configuration space remains a challenge for RRTs-based planners. This paper presents a novel two-stage approach to address the problem of multi-d.o.f. robot path planning in high-dimensional configuration space with narrow corridors. The first stage introduces an efficient sampling algorithm called Bridge Test to find a global roadmap that identifies the critical region. The second stage presents two varieties of RRTs, called Triple-RRTs, to search for a local connection under the guidance of the global landmark. The two-stage strategy keeps a fine balance between global heuristics and local connection, resulting in high performance over the previous RRTs-based path planning methods. We have implemented the Triple-RRTs planners for both rigid and articulated robots in two- and three-dimensional environments. Experimental results demonstrate the effectiveness of the proposed method.     

A roadmap construction algorithm for mobile robot path planning using skeleton maps

Path planning using conventional roadmaps, such as visibility graphs, probability roadmaps and skeleton maps, may have some disadvantages of long length, sharp turns or collisions with obstacles. Specifically, the paths using the conventional skeleton map have unnecessary turns around crossing points, which make longer paths and prevent the robot from moving smoothly. To improve the skeleton map, this paper proposes a new roadmap construction algorithm for path planning of a mobile robot using skeleton maps. The proposed algorithm alleviates the problems of the conventional algorithms by constructing roadmaps which consist of polygons around the crossing points. Simulation results show the efficiency of the proposed algorithm by comparing the results with those obtained using the conventional algorithm.     

Design of walking gaits for Tao-Pie-Pie,a small humanoid robot

A new way for multi-axis robot trajectory planning using a single cubic spline incorporating velocity and acceleration clipping is presented. Equations for velocity and acceleration clipping employing the cubic spline function for a single axis are derived. A robot tool-tip velocity vector magnitude clipping algorithm is proposed. Implementation for a fly-by and contour following trajectory control is discussed.     

Gaussian mixture-sound field landmark model for robot localization applications

This work proposes a novel Gaussian mixture-sound field landmark model for localization applications, based on the principle that sound fields produced by sources at different locations can be distinguished in terms of their statistical patterns. The experimental results indicate that two microphones are sufficient to differentiate among the patterns. The proposed method is robust against environmental noise and performs accurately in a complex environment. Moreover, it cannot only detect the non-line-of-sight locations when the direct path between the microphones and the location is blocked, but also can distinguish the locations aligned with respect to the line connecting the microphones. However, using only two microphones, these scenarios are difficult to handle by traditional direction-of-arrival or beamforming methods in microphone array research. The experiments were conducted on a quadruped robot platform with an eRobot agent using embedded Ethernet technology. Because of its high accuracy and low-cost, this method is suitable for robot localization in real environments. The experimental results also show that the proposed method with only two microphones outperforms the conventional multiple signal classification method (MUSIC) technique with six microphones at various signal-to-noise ratios.     

Three-Dimensional Path Planning of a Climbing Robot Using Mixed Integer Linear Programming

The City-Climber robot is a novel wall-climbing robot developed at The City College of New York that has the capability to move on floors, climb walls, walk on ceilings and transit between them. In this paper, we first develop the dynamic model of the City-Climber robot when it travel on different surfaces, i.e., floors, walls and ceilings, respectively. Then, we present a path planning method for the City-Climber robot using mixed integer linear programming (MILP) in three-dimensional (3-D) building environments that consist of objects with primitive geometrical shapes. MILP provides an optimization framework that can directly incorporate dynamic constraints with logical constraints such as obstacle avoidance and waypoint selection. In order to use MILP to solve the obstacle avoidance problem, we simplify and decouple the robot dynamic model into a linear system by introducing a restricting admissible controller. The decoupled model and obstacle can be rewritten as a linear program with mixed-integer linear constraints that account for the collision avoidance. A key benefit of this approach is that the path optimization can be readily solved using the AMPL and CPLEX optimization software with a MATLAB interface. Simulation results show that the framework of MILP is well suited for path planning and obstacle avoidance problems for the wall-climbing robot in 3-D environments.