Acquisition of obstacle motion patterns to improve mobile robot motion planning

Mobile robots for advanced applications have to act in environments which contain moving obstacles (humans). Even though the motions of such obstacles are not precisely predictable, usually they are not completely random; long-term observation of obstacle behavior may thus yield valuable knowledge about prevailing motion patterns. By incorporating such knowledge as statistical data, a new approach called statistical motion planning yields robot motions which are better adapted to the dynamic environment. To put these ideas into practice, an experimental system has been developed. Cameras observe the workspace in order to detect obstacle motion. Statistical data is derived and represented as a set of stochastic trajectories. This data can be directly employed in order to calculate collision probability, i.e. the probability of encountering an obstacle during the robot's motion. Further aspects of motion planning are addressed: path planning which minimizes collision probability, estimation of expected time to reach the goal and reactive planning.     

Global motion planning under uncertain motion, sensing, and environment map

Uncertainty in motion planning is often caused by three main sources: motion error, sensing error, and imperfect environment map. Despite the significant effect of all three sources of uncertainty to motion planning problems, most planners take into account only one or at most two of them. We propose a new motion planner, called Guided Cluster Sampling (GCS), that takes into account all three sources of uncertainty for robots with active sensing capabilities. GCS uses the Partially Observable Markov Decision Process (POMDP) framework and the point-based POMDP approach. Although point-based POMDPs have shown impressive progress over the past few years, it performs poorly when the environment map is imperfect. This poor performance is due to the extremely high dimensional state space, which translates to the extremely large belief space?B. We alleviate this problem by constructing a more suitable sampling distribution based on the observations that when the robot has active sensing capability, B can be partitioned into a collection of much smaller sub-spaces, and an optimal policy can often be generated by sufficient sampling of a small subset of the collection. Utilizing these observations, GCS samples B in two-stages, a subspace is sampled from the collection and then a belief is sampled from the subspace. It uses information from the set of sampled sub-spaces and sampled beliefs to guide subsequent sampling. Simulation results on marine robotics scenarios suggest that GCS can generate reasonable policies for motion planning problems with uncertain motion, sensing, and environment map, that are unsolvable by the best point-based POMDPs today. Furthermore, GCS handles POMDPs with continuous state, action, and observation spaces. We show that for a class of POMDPs that often occur in robot motion planning, given enough time, GCS converges to the optimal policy. To the best of our knowledge, this is the first convergence result for point-based POMDPs with continuous action space.     

Roadmap-based motion planning in dynamic environments

In this paper, a new method is presented for motion planning in dynamic environments, that is, finding a trajectory for a robot in a scene consisting of both static and dynamic, moving obstacles. We propose a practical algorithm based on a roadmap that is created for the static part of the scene. On this roadmap, an approximately time-optimal trajectory from a start to a goal configuration is computed, such that the robot does not collide with any moving obstacle. The trajectory is found by performing a two-level search for a shortest path. On the local level, trajectories on single edges of the roadmap are found using a depth-first search on an implicit grid in state-time space. On the global level, these local trajectories are coordinated using an A/sup */-search to find a global trajectory to the goal configuration. The approach is applicable to any robot type in configuration spaces with any dimension, and the motions of the dynamic obstacles are unconstrained, as long as they are known beforehand. The approach has been implemented for both free-flying and articulated robots in three-dimensional workspaces, and it has been applied to multirobot motion planning, as well. Experiments show that the method achieves interactive performance in complex environments.     

Polynomial joint angle arm robot motion planning in complex geometrical obstacles

This paper addresses a point-to-point of an arm robot motion planning in complex geometrical obstacle. It will govern a two-layer optimization strategy utilizing sixth degree polynomial as joint angle path. At the beginning of the motion planning process, the path planning starts with the optimization objective to minimize the joint angle travelling distance under collision detection rules as constraint. After the best path has been met, the associated time will be searched with the optimization objective to minimize the total travelling time and the torque under the maximum velocity, the maximum acceleration, the maximum jerk, and the maximum torque constraints. The performance of a Genetic Algorithm (GA) and a Particle Swarm Optimization (PSO) will be investigated in searching the feasible sixth degree polynomial joint angle path and the total travelling time that gives the optimal trajectories under kinodynamic constraints. A 3-Degree-Of-Freedom (3-DOF) planar robot will be utilized to simulate the proposed scenario.     

Temporal logic motion planning for dynamic robots

In this paper, we address the temporal logic motion planning problem for mobile robots that are modeled by second order dynamics. Temporal logic specifications can capture the usual control specifications such as reachability and invariance as well as more complex specifications like sequencing and obstacle avoidance. Our approach consists of three basic steps. First, we design a control law that enables the dynamic model to track a simpler kinematic model with a globally bounded error. Second, we built a robust temporal logic specification that takes into account the tracking errors of the first step. Finally, we solve the new robust temporal logic path planning problem for the kinematic model using automata theory and simple local vector fields. The resulting continuous time trajectory is provably guaranteed to satisfy the initial user specification.     

Trajectory time scaling of a mobile robot to avoid dynamic obstacles on the basis of the INLVO

To ensure the collision safety of mobile robots, the velocity of dynamic obstacles should be considered while planning the robot’s trajectory for high-speed navigation tasks. A planning scheme that computes the collision avoidance trajectory by assuming static obstacles may result in obstacle collisions owing to the relative velocities of dynamic obstacles. This article proposes a trajectory time-scaling scheme that considers the velocities of dynamic obstacles. The proposed inverse nonlinear velocity obstacle (INLVO) is used to compute the nonlinear velocity obstacle based on the known trajectory of the mobile robot. The INLVO can be used to obtain the boundary conditions required to avoid a dynamic obstacle. The simulation results showed that the proposed scheme can deal with typical collision states within a short period of time. The proposed scheme is advantageous because it can be applied to conventional trajectory planning schemes without high computational costs. In addition, the proposed scheme for avoiding dynamic obstacles can be used without an accurate prediction of the obstacle trajectories owing to the fast generation of the time-scaling trajectory.     

Neuro-fuzzy and model-based motion control for mobile manipulator among dynamic obstacles

This paper focuses on autonomous motion control of a nonholonomic platform with a robotic arm, which is called mobile manipulator. It serves in transportation of loads in imperfectly known industrial environments with unknown dynamic obstacles. A union of both procedures is used to solve the general problems of collision-free motion. The problem of collision-free motion for mobile manipulators has been approached from two directions, Planning and Reactive Control. The dynamic path planning can be used to solve the problem of locomotion of mobile platform, and reactive approaches can be employed to solve the motion planning of the arm. The execution can generate the commands for the servo-systems of the robot so as to follow a given nominal trajectory while reacting in real-time to unexpected events. The execution can be designed as an Adaptive Fuzzy Neural Controller. In real world systems, sensor-based motion control becomes essential to deal with model uncertainties and unexpected obstacles.     

Robust neuro-fuzzy sensor-based motion control among dynamic obstacles for robot manipulators

A new robust neuro-fuzzy controller for autonomous and intelligent robot manipulators in dynamic and partially known environments containing moving obstacles is presented. The navigation is based on a fuzzy technique for the idea of artificial potential fields (APFs) using analytic harmonic functions. Unlike the fuzzy technique, the development of APFs is computationally intensive. A computationally efficient processing scheme for fuzzy navigation to reasoning about obstacle avoidance using APF is described, namely, the intelligent dynamic motion planning. An integration of a robust controller and a modified Elman neural networks (MENNs) approximation-based computed-torque controller is proposed to deal with unmodeled bounded disturbances and/or unstructured unmodeled dynamics of the robot arm. The MENN weights are tuned online, with no off-line learning phase required. The stability of the overall closed-loop system, composed by the nonlinear robot dynamics and the robust neuro-fuzzy controller, is guaranteed by the Lyapunov theory. The purpose of the robust neuro-fuzzy controller is to generate the commands for the servo-systems of the robot so it may choose its way to its goal autonomously, while reacting in real-time to unexpected events. The proposed scheme has been successfully tested. The controller also demonstrates remarkable performance in adaptation to changes in manipulator dynamics. Sensor-based motion control is an essential feature for dealing with model uncertainties and unexpected obstacles in real-time world systems.     

The complexity of the free space for motion planning amidst fat obstacles

The complexity of motion planning algorithms highly depends on the complexity of the robot's free space, i.e., the set of all collision-free placements of the robot. Theoretically, the complexity of the free space can be very high, resulting in bad worst-case time bounds for motion planning algorithms. In practice, the complexity of the free space tends to be much smaller than the worst-case complexity. Motion planning algorithms with a running time that is determined by the complexity of the free space therefore become feasible in practical situations. We show that, under some realistic assumptions, the complexity of the free space of a robot with any fixed number of degrees of freedom moving around in ad-dimensional Euclidean workspace with fat obstacles is linear in the number of obstacles. The complexity results lead to highly efficient algorithms for motion planning amidst fat obstacles.Research is supported by the Dutch Organization for Scientific Research (NWO) and partially supported by the ESPRIT III BRA Project 6546 (PROMotion).     

Modeling dynamic scenarios for local sensor-based motion planning

This paper addresses the modeling of the static and dynamic parts of the scenario and how to use this information with a sensor-based motion planning system. The contribution in the modeling aspect is a formulation of the detection and tracking of mobile objects and the mapping of the static structure in such a way that the nature (static/dynamic) of the observations is included in the estimation process. The algorithm provides a set of filters tracking the moving objects and a local map of the static structure constructed on line. In addition, this paper discusses how this modeling module is integrated in a real sensor-based motion planning system taking advantage selectively of the dynamic and static information. The experimental results confirm that the complete navigation system is able to move a vehicle in unknown and dynamic scenarios. Furthermore, the system overcomes many of the limitations of previous systems associated to the ability to distinguish the nature of the parts of the scenario.

Path deformation method for robot motion planning problems in the presence of obstacles

This paper studies the following path planning problem for a robot. There is a given path avoiding obstacles. If existing obstacles change their location or new obstacles appear, the preplanned path must be appropriately deformed for all obstacles avoidance. We develop a solution approach based on the component-wise method of smoothing the path curvature and the method of potentials. The proposed approach enables to avoid obstacles and smooth the path and its curvature (in the 2D and 3D cases).     

Nonholonomic multibody mobile robots: Controllability and motion planning in the presence of obstacles

We consider mobile robots made of a single body (car-like robots) or several bodies (tractors towing several trailers sequentially hooked). These robots are known to be nonholonomic, i.e., they are subject to nonintegrable equality kinematic constraints involving the velocity. In other words, the number of controls (dimension of the admissible velocity space), is smaller than the dimension of the configuration space. In addition, the range of possible controls is usually further constrained by inequality constraints due to mechanical stops in the steering mechanism of the tractor. We first analyze the controllability of such nonholonomic multibody robots. We show that the well-known Controllability Rank Condition Theorem is applicable to these robots even when there are inequality constraints on the velocity, in addition to the equality constraints. This allows us to subsume and generalize several controllability results recently published in the Robotics literature concerning nonholonomic mobile robots, and to infer several new important results. We then describe an implemented planner inspired by these results. We give experimental results obtained with this planner that illustrate the theoretical results previously developed.This research was partially funded by DARPA contract DAAA21-89-C0002 (Army), CIFE (Center for Integrated Facility Engineering), and Digital Equipment Corporation.     

Hierarchical incremental path planning and situation-dependent optimized dynamic motion planning considering accelerations.

This paper studies a hierarchical approach for incrementally driving a nonholonomic mobile robot to its destination in unknown environments. The A* algorithm is modified to handle a map containing unknown information. Based on it, optimal (discrete) paths are incrementally generated with a periodically updated map. Next, accelerations in varying velocities are taken into account in predicting the robot pose and the robot trajectory resulting from a motion command. Obstacle constraints are transformed to suitable velocity limits so that the robot can move as fast as possible while avoiding collisions when needed. Then, to trace the discrete path, the system searches for a waypoint-directed optimized motion in a reduced 1-D translation or rotation velocity space. Various situations of navigation are dealt with by using different strategies rather than a single objective function. Extensive simulations and experiments verified the efficacy of the proposed approach.     

A quick intelligent control system for a mobile robot to avoid collision with moving obstacles

This paper proposes a concept of initial minimum safety spacing (IMSS) for a robot to avoid the collision with moving obstacles from any direction. A quick intelligent control system based on IMSS to avoid the collision is presented. In the system, the necessary deceleration and steering can be predicted using the fuzzy reasoning, which only needs to input one variable of the collision danger degree judged according to IMSS. So, the membership functions and the fuzzy rules are very simple, the calculation time for the avoidance is reduced. These advantages are verified by the numerical simulation results.     

Experimental study on autonomous mobile robot acquiring optimal action to avoid moving obstacles

The principal aim of this study was to show how an autonomous mobile robot can acquire the optimal action to avoid moving multiobstacles through interaction with the real world. In this paper, we propose a new architecture using hierarchical fuzzy rules, a fuzzy evaluation system, and learning automata. By using our proposed method, the robot autonomously acquires finely tuned behavior which allows it to move to its goal and avoid moving obstacles by using the steering and velocity control inputs simultaneously. We also show experimental results which confirm the feasibility of our method.     

Autonomous mobile robot dynamic motion planning using hybrid fuzzy potential field

A new fuzzy-based potential field method is presented in this paper for autonomous mobile robot motion planning with dynamic environments including static or moving target and obstacles. Two fuzzy Mamdani and TSK models have been used to develop the total attractive and repulsive forces acting on the mobile robot. The attractive and repulsive forces were estimated using four inputs representing the relative position and velocity between the target and the robot in the x and y directions, in one hand, and between the obstacle and the robot, on the other hand. The proposed fuzzy potential field motion planning was investigated based on several conducted MATLAB simulation scenarios for robot motion planning within realistic dynamic environments. As it was noticed from these simulations that the proposed approach was able to provide the robot with collision-free path to softly land on the moving target and solve the local minimum problem within any stationary or dynamic environment compared to other potential field-based approaches.     

Motion planning in uncertain environments with vision-like sensors

In this work we present a methodology for intelligent path planning in an uncertain environment using vision-like sensors, i.e., sensors that allow the sensing of the environment non-locally. Examples would include a mobile robot exploring an unknown terrain or a micro-UAV navigating in a cluttered urban environment. We show that the problem of path planning in an uncertain environment, under certain assumptions, can be posed as the adaptive optimal control of an uncertain Markov decision process, characterized by a known, control-dependent system, and an unknown, control-independent environment. The strategy for path planning then reduces to computing the control policy based on the current estimate of the environment, also known as the “certainty-equivalence” principle in the adaptive control literature. Our methodology allows the inclusion of vision-like sensors into the problem formulation, which, as empirical evidence suggests, accelerates the convergence of the planning algorithms. Further we show that the path planning and estimation problems, as formulated in this paper, possess special structure which can be exploited to significantly reduce the computational burden of the associated algorithms. We apply this methodology to the problem of path planning of a mobile rover in a completely unknown terrain.     

New optimization method to solve motion planning of dynamic systems: application on mechanical manipulators

In this paper, a new method is proposed to solve a nonlinear optimal control problem and determine the Dynamic Load-Carrying Capacity (DLCC) of fixed and mobile manipulators in point-to-point motion. Solution methods for designing nonlinear optimal controller in closed loop form are usually based on indirect methods, but the proposed method is a combination of direct and indirect methods. The optimal control law with state feedback form, for nonlinear dynamic systems, is given by the solution to the nonlinear Hamilton–Jacobi–Bellman (HJB) equation. The Galerkin procedure and a nonlinear optimization algorithm are used to solve this equation numerically. Another innovation of this paper is optimal trajectory planning, which is done simultaneously with the controller design procedure. Finally, a new algorithm is developed to find DLCC of manipulators and the related optimal trajectory using proposed method. The validity of the method is demonstrated via simulation and experimental tests for a fixed manipulator and two-link wheeled mobile manipulator named Scout.     

Velocity potential approach to path planning for avoiding moving obstacles

This paper describes the theory and an experiment of a velocity potential approach to path planning and avoiding moving obstacles for an autonomous mobile robot by use of the Laplace potential. This new navigation function for path planning is feasible for guiding a mobile robot avoiding arbitrarily moving obstacles and reaching the goal in real time. The essential feature of the navigation function comes from the introduction of fluid flow dynamics into the path planning. The experiment is conducted to verify the effectiveness of the navigation function for obstacle avoidance in a real world. Two examples of the experiment are presented; first, the avoidance of a moving obstacle in parallel line-bounded space, and second, the avoidance of one moving obstacle and another standing obstacle. The robot can reach the goal after successfully avoiding the obstacles in these cases.