Magnitude of field of the point at the trajectory.
This chapter introduces two kinds of motion path planning algorithms for mobile robots or unmanned ground vehicles (UGV). First, we present an approach of trajectory planning for UGV or mobile robot under the existence of moving obstacles by using improved artificial potential field method. Then, we propose an I-RRT* algorithm for motion planning, which combines the environment with obstacle constraints, vehicle constraints, and kinematic constraints. All the simulation results and the experiments show that two kinds of algorithm are effective for practical use.
- path planning
- trajectory planning
- mobile robots
- unmanned ground vehicles (UGV)
In recent years, the intelligent mobile robots have played an important role in industry, agriculture, aerospace, and space exploration, and it becomes a hotspot issue in many research fields. The robot is divided into two categories from the application environment, named industrial robots and special robots. The industrial robot is industrial oriented multi-joint manipulator or multi-degree of freedom robot, while the special robot is opposite to industrial robots, which is used for non-manufacturing environment or service including service robots, underwater robot, entertainment robot, military robots, agricultural robots, and robotic machines. If we want the robot autonomous mobile in configuration space, the very first thing we will do is the path planning, which can be defined as the process of finding a collision-free path for a robot from its initial position to the goal or target point by avoiding collisions with any static obstacles or other agents present in its environment. In order to solve these problems, many domestic and foreign scholars researched and put forward many theories and methods of the path planning [1, 2, 3, 4]. The traditional path planning algorithms, such as ant colony algorithm, genetic algorithm, and artificial potential field algorithm, dealing with some motion planning have its unique superiority. In addition, the algorithm based on potential field or heuristic function, such as A*, D*, and artificial potential field method, in addressing the problem of planning can meet the requirements of real-time and the optimality. This chapter introduces two kinds of path planning algorithm of the robot, including mobile robots and unmanned ground vehicles (UGV).
2. Path planning for robots with existence of moving obstacles
In this chapter, we present an approach of the ground mobile vehicle or robot trajectory planning under the existence of moving obstacles by using improved artificial potential field method. The potential field intensity and strength instead of force vectors was adopted in the planning. Considering the speed effect of mobile obstacles and mobile robot, the velocity information was introduced into potential field function and an “added potential field” was also applied to guide the mobile robot to be free of collision with local obstacles. Based on the new method, all the potential field intensity was considered and summed by algebraic style, then the genetic trust region algorithm was used to search the minimum sum points of potential field intensity within the motion space and scope, which the mobile robot can reach target during a sampling period, and the global optimization trajectory was consisted of all the minimum points. Simulation and experiment results show that better results of path planning for a mobile robot in a complex environment with the existence of moving obstacles can be achieved using this new approach.
The problem of mobile robot path planning under a dynamic environment in mobile robot domain is hot and difficult. Its task is to find a path, which is from the initial state to goal state. Currently, common path planning methods are artificial potential field method, grid method, neural network method, chaos genetic algorithm, aand so on [5, 6]. Artificial potential field method in the algorithm of path planning is relatively mature and efficient, because of the simplicity of the mathematical calculation, it is widely used. However, there are the issues of local minimum point and destination unreachable in traditional artificial potential field method. There are a variety of ways to escape from the local minimum point, such as random fleeing method, heuristic search, walking along the wall, Tangent bug’s method, and so on [7, 8], These methods need to apply an additional control force to the robot, which could not fundamentally solve problems. An improved artificial potential field method based on genetic algorithm was proposed in  to solve the problem of goal unreachable and local minimum, but the convergent speed of the algorithm still needs to be improved.
In this chapter, aimed at the shortcoming of traditional artificial potential field method, an improved artificial potential field applied in a dynamic environment is proposed. Firstly, an improved artificial potential field model is established; then the genetic trust region algorithm is applied to solve the sub-target point problem of the improved artificial potential field model and then the optimal path is planned.
2.1. Artificial potential field model
2.1.1. The shortcoming of traditional potential field model
There are some problems when this method is applied to robot path planning:
Because the traditional artificial potential field method applies virtual force to control the movement of the robot, it is possible for a robot that it cannot go through a narrow passage when two obstacles are near to each other. Moreover, if robot, obstacles and target point are on the same straight line, the robot controlled by force can only move on the straight line repeatedly, but it cannot reach to the target point.
If obstacles are near to target point, it will be possible that repulsive force is greater than attractive force, leading to the problem of goal unreachable (GNRON).
The robot has not yet arrived at target point nearly, however, the summation of suffered forces is zero, consequently, it will fall in local minimum point and stop moving.
2.1.2. Improved measures
Aimed at the defects of traditional artificial potential field model, improved measures are proposed as below:
Turning the attractive force of target to the robot and the repulsive force of obstacles to the robot into a kind of potential field intensity, a method of calculating potential field is applied to replace traditional vector force control.
Adding a coefficient entry in the gravitational potential of obstacles, when the robot is close to the target point, gravitational potential is reducing as well as repulsion potential. Finally, they are zero until the robot arrives at the target point, so the problem of obstacles and target point being too close causing goal unreachable.
For a “deadlock” issue caused by local minimum point, the “added potential field” is introduced to guide the robot to walk out the local minimum point, that is, adding an extra potential field .
2.1.3. Improved potential model
According to above improved measures, the improved artificial potential field model is proposed. The attractive force model of the target to a full range of vehicle’s body is:
where is the distance between the current location of the central point of mobile vehicle’s body and target point; k is a proportional gain coefficient; X is the position of robot’s central point in movement space; and is the target point position .
Repulsive potential model of the i-th static obstacles on the full range of movement of the body is:
where , n is the summation of static obstacles; is the shortest distance of between current location of the center of mobile vehicle’s body and the i-th obstacle; the effective effect distance of obstacle; and is proportional position gain coefficient.
Dynamic obstacles are in motion, and it cannot reflect environment information completely if only taking location into consideration. Bring the relative speed of dynamic obstacles and robots into potential field function, Repulsive potential model of the i-th static obstacles on the full range of movement of the body is got:
where , m is the summation of mobile obstacles; is proportional coefficient; V is the current speed of the mobile body, ; is the current speed of the r-th dynamic obstacles; is the current movement direction of the mobile body; and is the current movement direction of the r-th dynamic obstacle.
When the robot is in local minimum point, the “added potential” is brought to figure the problem of local minimum out, the added potential model is:
where judgment distance of whether the mobile body reaches to a target point; s is a proportional coefficient.
Therefore, the whole potential field intensity of a range of mobile body is shown in (2). When the robot is in local minimum point, taking (2) plus the added potential as the total potential field value (as shown in (2)).
Based on above model, every sampling period all regard the minimum point of potential field sum as a sub-goal point, and multiple sub-target is consisted of global optimization path. The sum of potential field is shown in (2). In order to avoid the case of target vibrating in the vicinity of local minimum point, vector synthesis method is used to judge whether the robot is in local minimum point, if in the local minimum point, potential field sum contains added potential, as shown in (3). Assuming the maximum speed of robot is , the sampling period is , so when robot in the reachable range of every sampling period, it takes current location as a center, and is a radius of the circle. The speed of robot movement should not too big or too small in order to ensure the stability of robot movement and performing efficiency, so a sub-goal point can be chosen from an annular region, .
As Figure 1 shows, the shaded part of the annular region is the optional region of the sub-target point. Therefore, solving the sub-target issue is the key to improve artificial potential field method.
2.2. Solving target point based on genetic trust region
In order to improve the efficiency of path planning, below two situations will be considered:
(1) When the robots move in the free space far away from obstacle (), that solving the minimum point of the sum of annular region potential field intensity shown in Figure 1. The trust region method in optimal search algorithm has good reliability and fast convergence, which offers a new idea to solve the sub-target. However, its iteration speed sometimes is affected by the radial trust. When the iteration speed is affected by the radius of trust region, using genetic algorithms to solve a point, which is better than one in the current iteration point, then, based on the point the trust region is restarted until the optimized point is found, which can greatly improve the convergence speed of algorithm [9, 10, 11].
The points of the shaded part can show as . Therefore, Eqs. (2) and (3) are the function about variables R and , assuming . Using genetic trust region algorithm to solve the target function of sub-goal point as (4) shows, in other words, that solving a class of linear constrained optimized problem, when that the robot is located in local minimum point, (4) and added potential are regarded as the target function.
Using quadratic approximation and constructing constrained trust region sub-problem:
where is the radius of trust region; solving is very complicated, and using BFGS formula of quasi-Newton to structure Hessian matrix , which is approximate to . is the decline tentative step. is the range of R and .
The algorithm contains, and remark shows: := value assignment, , the amount of actual decline in the ratio of the amount of pre-estimated decline is:
The first step in the algorithm.
Step 1: Initialization, given: , , .
Step 2: Calculating , if , stop calculating, and output the result.
Step 3: Solving sub-problem in Eq. (5), and get the decline tentative step .
Step 4: Calculating , if meanwhile , so, rectifies , or , .
Step 5: Choosing , let it meet:
Step 6: If , and using genetic algorithm to quickly solve min so that an iteration point which is better than the current point, go to step 7, Or back to step 8.
Step 7: If , so order back to step 2; or back to step 8.
Step 8: Using BFGS formula to modify and gets , back to step 2.
values can be adjusted to control the number of times the call number of sub-issues of a genetic algorithm to achieve the optimization algorithm speed, regulating also can regulate the speed of convergence of the algorithm, but there are trade-offs to optimize the value obtained, need to be considered in accordance with the actual situation.
When the convergence speed is influenced by the radius of the trust region in step 6 of algorithm 1, using a genetic algorithm to figure out must meet:
when solving , are all known quantity.
Fitness function: establishing the mapping relationship between the objective function and the function of moderate: ; adopting the binary code to encode; replication strategy to preserve the best individual mixed roulette selection; crossover operator is single point crossover; and mutation operator for the basic bit mutation.
The procedure of algorithm 2:
Step 1: Parameter initialization: population size N, crossover probability , mutation probability , current algebraic , maximum algebraic , and . The coding initial solution produces a unit corresponding to the initial solution. And it randomly produces two l-bit binary string working as one unit, and it does not stop until it generates N units.
Step 2: Solving adaption value of every individual in the current group, to get the optimization : described as:
, stopping calculating, and backing to the step1 of algorithm 1.
ELSE backing to step 3.
ELSE updating initial parameters, baking to step 1.
Step 3: Replacing the two worst individuals in the two optimizations of the current generation, then selecting N individuals by using roulette selection.
Step 4: Manipulating cross mutation to produces a new population. Backing to step 2.
2.3. Simulation and experiment
We select the initial parameters of the algorithm:
. The speed of mobile obstacles.
0.2(0.5) + r and (m)/s,
The original point of robots is (0, 0), the target point is (20, 24), and the unit is m (meter).
The simulation results are shown in Figures 4 and 5. It can be seen from simulation, that to combine trust region algorithm and the improved artificial potential field method can optimize mobile robot path planning, and get a better solution to local minima and the unreachable target problem. Under the same conditions, a pure genetic algorithm for solving the sub-goal problem, the average convergence time comes to the second level, and the individual points solvers need more than 30 s, therefore, the proposed algorithm is much fast.
Robot trajectory simulation resulting potential field on a typical point 1 seen from Table 1, the optimal path in the intensity values obtained are shown in table potential field strength decreases rapidly, and the strong field in the times to reach the target point, the basic value to 30 s.
To verify the validity of the path planning algorithm, an experiment was made based on the current conditions as shown in Figures 2 and 3. The equipment used in the experiment include mobile robot, laser tracker sensor, distance detector sensor, digital compass, dynamics obstacles, and still obstacles.
The laser tracker can precisely measure the center point of the coordinate (x, y) when mobile robot is in motion. Then it can send the distance information to the robot controller through a local network and get the location of the robot in the space. The mobile robot is shaped like a cylinder, with 0.6 m in diameter, 12 ultrasonic distance detect sensors with 0.1–6.0 m detect distance, and 32 infrared distance sensors with 0.1–0.8 m detect distance. The angle between two adjacent sensors is 30°. The measurement time is 0.015 s. The initial position of the robot is (1.375, −2.328), and the target position is (1.248, 1.353), the velocity of moving obstacle is Vr = 0.08 m/s, and . The velocity of the mobile robot is V = 0.05 m/s, the moving direction can be measured in real-time by the digital compass.
The initial parameters of the experiment are k = 1, n = 2, m = 1 . The laser tracker recorded many points of the mobile robot, and the approximated trajectory can be obtained from these points as shown in Figures 4 and 5. And the relationship between the field strength and algorithm implementation time was listed in Table 2. From the experiment, we can see that the algorithm has some advantages compared with those traditional methods. It is faster in implementation and computation.
We presented an approach of mobile robot trajectory planning under the existence of moving obstacles by using improved artificial potential field method. To further verify the improved artificial potential field method for moving machines effectiveness of robots path planning, the use of the existing conditions, design path planning experiment = experimental scene shown in “laboratory equipment including full orientation of the mobile robot laser tracker digital distance sensor compass static obstacles and dynamic obstacles. Laser tracker can accurately measure mobile robot motion moving the coordinate value of the center point of the process (x, y), through a wireless local area network location information measured in real-time sent to the robot controller, robot positioning cylindrical omnidirectional mobile robot structure with a diameter 0.6 m, and surrounded by 12 uniform ultrasonic ranging.
3. Improved RRT* motion planning algorithm for mobile robot
Some path planning algorithms such as ant colony algorithm, genetic algorithm, artificial potential field algorithm, and dealing with some planning have its unique superiority. However, in the complex environment and high-dimensional space, the complex of the algorithm will increase sharply, which lead the convergence time too long to solve the problem. Because the algorithm based on potential field or heuristic function does not consider the kinematic and dynamic constraints, its result cannot be executed by the real case [12, 13, 14, 15, 16, 17].
In order to solve the problem of high-dimensional path planning, the sampling algorithms have been introduced . Compared with another advanced algorithm, the main advantage of the algorithm based on sampling is avoiding constructing the explicit configuration space, and it has been shown to be an effective solution to the path planning . RRT algorithm based on sampling with rapid convergence rate can be used in unknown obstacle environment . However, there are still some shortcomings in RRT algorithm [21, 22, 23]:
Its convergence rate is very slow in achieving the optimal solution;
Its memory requirements are significantly large due to a large number of iterations used to calculate the optimal path;
The rejection of samples, which might not be connectable directly with the existing nodes in the tree, but may lie closer to the goal region and hence could aid the algorithm in determining an optimal path much more rapid.
The domestic and foreign scholars have been studied on these deficiencies and proposed various RRT algorithms to adapt to different application scenarios. In order to improve the efficiency of the expansion of the node, Kuffner and La Valle proposed the RRT-connect . Karaman and Frazzoli first proposed RRT* algorithm, which convergence to the optimal solution . A.H. Qureshi and S. Mumtaz proposed the TG-RRT*, using triangular geometry to select node, in order to reduce the number of iterations required for the optimal solution, so as to make the algorithm rapid convergence . C. Wouter Bac and Tim Roorda proposed by RRT algorithm on ROS platform for mobile robot path planning research and applied to the motion planning problem in the dense obstacles environment .
3.1. Nonholonomic constraints for mobile robot
The integrity constraints include a system of generalized coordinates derivative and integral constraints. The mobile robot is a typical nonholonomic constraint system. The mobile robot’s simplified moving model is shown in the Figure 6.
Mobile robot’s state variables in configuration space , let represent the center of mobile robot rear axle in the system coordinates, represent the angle between the forward direction of the mobile robot and the x-axis, represent the angle between the forward direction of the mobile robot and the front wheel direction, as the speed of the mobile robot, due to the nonholonomic constraints, the wheel is point contact with the ground, and only pure roll no relative sliding at contact.
And the constraint equations:
(acceleration) and (angular acceleration) of the mobile robot control variables. The minimum turning radius (maximum curvature) of the mobile robot is:
Therefore, it is unreasonable without considering the nonholonomic constraints of the robot planning algorithm.
3.2. Description and implementation of the I-RRT*
I-RRT* algorithm showed in Table 3 is specifically designed for motion planning in complex, cluttered environments where exploration of configuration space is difficult. Let the sets of near vertices from the tree and be denoted by and , respectively. The path is connecting and is denoted by , while the path is connecting and is denoted by .
It starts by picking a random sample from the obstacle-free configuration space that is, . It then populates the set of near vertices, for both trees using the procedure. It should be noted that a ball region centered at of radius r is formed, and the sets of the near vertices from both trees are computed that is:
In the case of both sets of near vertices being found empty, these sets are filled with the closest vertex from their respective trees instead. The procedure Best Selected Tree returns the nearest vertex on the Best Selected Tree, which is eligible to become the parent of the random sample.
Hence, unlike the connect heuristic, the I-RRT* is not greedy since the connection is only made inside the ball region. Finally, the tree connection generates the end-to-end global path.
3.3. Experimental results
3.3.1. The algorithm simulation
This section presents simulations performed on a 2.4 GHz Intel Core i5 processor with 4 GB RAM. Here, performance results of our I-RRT* algorithm are compared with RRT* and B-RRT*. For proper comparison, experimental conditions and size of the configuration space were kept constant for all algorithms. Since randomized sampling-based algorithms exhibit large variations in results, the algorithms were run up to 50 times with different seed values for each type of environment. Maximum, minimum, and an average number of iterations i as well as time t utilized by each algorithm to reach the optimal path solution is presented in Table 4.
In the second environment simulation, chooses some representative to verify the algorithm performance.
In the third environment model simulation test, using the three different kinds of obstacle environment simulation experiment, we tested the performance of the algorithm in Figure 10.
To restrain the computational time within reasonable limits, the maximum limit for the number of tree nodes was kept at 3 million.
Although both I-RRT* and B-RRT* were successful in finding the optimal solution, B-RRT* took an extremely large number of iterations to converge in comparison with I-RRT*. B-RRT* utilizes the partial greedy heuristic approach as discussed earlier, which significantly reduces its ability of convergence to the optimal path solution. Table 4 shows the convergence from the initial path solution to the optimal path solution by I-RRT* and RRT*, respectively. For determination of the optimal path, the I-RRT* algorithm takes the least number of average iterations (iavg = 111,139) as compared to B-RRT*(iavg = 498,972) and the extraordinarily large number of iterations taken up by RRT*(iavg = 1,437,342).
3.4. Mobile robot simulation experiment on ROS
3.5. Static environment experiment
Using the I-RRT* algorithm for mobile robot path planning, we choose a random target on the map and set the position and posture in Figure 13. I-RRT* algorithm can generate a barrier-free path, as shown in the green feed, where the trajectory planning algorithm.
Figures show the I-RRT* dynamic planning process, which is real-time planning. I-RRT* algorithm programming device receives the message, if there are new obstacles, in order to avoid obstacles, I-RRT* real-time planning. In this picture perceived color area for mobile robot around obstacles of information, the green line is the initial path planning, the red line for real-time planning path. As a result, the algorithm can be applied to the dynamic environment of the path planning problem.
Solving the path planning problems of the ground robot and mobile robot are the premise of more efficient use of the robot. Due to the different types of robots, the problems in the path planning need to be considered, from 2D to 3D. Three path planning algorithms for different types of robots are proposed in this chapter. The problem of path planning for existing industrial robots and mobile robots, including unmanned vehicles and unmanned aerial vehicles, are solved. All the simulations results show that the algorithms proposed in this paper are feasible.
This research is supported in part by Natural Science Foundation of China (NSFC) No. 51405001 and 31300125.