Path planning for mobile articulated robots based on the improved A* algorithm

Abstract

Mobile articulated robots system composed of tractor and multiple articulated trailers is a nonlinear and underactuated system subject to nonholonomic constraints. The significant achievements of path planning for mobile robots with single segment are very difficult to be applied to it directly. For resolving this problem, the kinematics model is established for the system with three segments connected by nonstandard connection type, as well as its trajectory. Equivalent size is introduced that includes two parameters: the distance parameter being the size for enlarging obstacles and the curvature parameter being the minimum turning radius of system. The distance parameter is used to enlarge obstacles in the environment to shrink the system to be a particle. The planning path adopted by the improved A* algorithm can ensure itself as a collision-free and feasible path as long as the maximum path curvature is no larger than the curvature parameter in free space. The comparisons of simulation result show that the improved A* algorithm makes the quality of path optimized and more suitable than A* algorithm under the complex environment.

Keywords

Mobile articulated robots system path planning equivalent size distance parameter curvature parameter improved A* algorithm

Introduction

The control of a compact tractor-trailer using an electrical vehicle can improve the working efficiency and increase the load transportation capacity.¹ Mobile articulated robots has become one of the most welcomed and popular electronic devices in automated factories, airport, railway station, and shipping wharf to accomplish the tasks of materials transmission, baggage handling, and goods transshipments. In addition, it is used for many applications with different goals in rescue environments such as reconnaissance, hazard identifications, and victim detection. Therefore, it is considered to have extensive prospect nowadays.

Mobile articulated robot composed of several segments (e.g. tractor and multiple articulated trailers) is a nonlinear and underactuated system subject to nonholonomic constraints.^1,2 Compared with mobile robot with single segment, the study of kinematics and motion control of mobile articulated robots system can be very complicated. In order to implement path planning effectively, it is necessary to establish the corresponding kinematics model, such as tractor-trailer wheeled robot,³ center-articulated mobile robot,⁴ the general one-trailer system,⁵ mobile articulated robots with two trailers,⁶ articulated tricycle for agriculture,⁷ mobile robots with N-trailers,^8,9 and so on. Over the last few decades, a great number of studies have been devoted to path planning for the mobile articulated robots, and different approaches have been proposed. Nayl et al.¹⁰ analyzed the effect of kinematic parameters on a novel proposed online motion planning algorithm for an articulated segment based on model predictive control. Lamiraux et al.¹¹ dealt with the motion planning and control for the mobile robot Hilare pulling a trailer. Carlos et al.¹² presented a nonlinear feedback control law and a method of path reconstruction for the rear carts for a train-like segment used in dangerous environments.

A* algorithm is a method of path planning in known global environments and also applies to path quadratic programming.¹³ For example, a simple but very effectual method is proposed to make the A* algorithm suitable for dynamic local path planning in real time.¹⁴ Trovato and Dorst¹⁵ proposed differential A* algorithm to solve the problem of path planning under the condition of local environmental information changes. However, there are some issues in the A* algorithm and the differential A* algorithm, such as many broken lines and turn times. Moreover, the processing of the differential A* algorithm is complicated and computationally costly. Although product development using improved A* algorithm has been drawing much attention from academics as well as corporate world, research into mobile articulated robots system is still rarely underdeveloped. This article deals with the path planning from an initial position to a goal position for mobile articulated robots. The improved A* algorithm model is established and is compared with A* algorithm to improve the quality of planning path. However, there are some constraints in mobile articulated robots system, such as incomplete constraints in the motions of each segment, the axial angle constraints among the segments, and the steering angle constraint leaded by the steering mechanism of tractor. It is these factors that make the significant results of path planning of single segment mobile robot are very difficult to apply directly to the system. Accordingly, this article elaborates the process of employing equivalent size (ES) to enlarge obstacles in static workspace so as to plan path effectively for this kind of robot.

The remainder of this article is organized as follows. The second section presents the description and analysis of the motion of mobile articulated robots system. The third section focuses on the path planning for the system based on the improved A* algorithm. Simulations of path planning based on the A* algorithm and the improved A* algorithm are performed in “Simulation results” section. Finally, conclusions of this work and the future tasks are given in “Conclusion” section.

Description and analysis of the system motion

Mobile articulated robots system can be categorized into standard link and nonstandard link according to the position of join point. The standard form is defined as the join point lies on the midpoint on rear axle of the former body, and the nonstandard one on the intersection of two connecting rods. Actually, the standard form can be regarded as the special status of the nonstandard form. Mobile articulated robots system with three segments connected by nonstandard form is regarded as research subject in this article, as shown in Figure 1. Kinematics equation is well-known for describing the relations between the system configuration against time or derivative of other variables. The verse kinematics problem is that how to calculate the configuration of each segment with the given control inputs of tractor drive and steering mechanisms. Trajectories of each segment are varied during the movements unless the system moves in a straight line. The width of trajectories swept by the entire system is variable. Therefore, it has brought higher demands to the motion planning. The trajectory is analyzed to provide important reference information for the path planning based on the kinematics equation of the system.

Figure 1.

Coordinate system of mobile articulated robots with three segments.

Kinematics model

Suppose that each segment is considered as rigid body with the same width and is symmetric about its longitudinal axis. As the first segment of the system, the tractor has three wheels and the front one plays the role of both driving and directing action. As a nonholonomic system, this system has non-integrable velocities restrictions. The nonholonomic restriction for the first segment is given by $\dot{y} cos θ - \dot{x} sin θ = 0$ . It means that the motion of robot is pure rolling style with no slip.

Establishment of the coordinate system

The coordinate system of mobile articulated robots with three segments is shown in Figure 1, in which the reference frame (i.e. the absolute coordinate system) XOY is established firstly with O set as the coordinate origin, and then the coordinate systems of each segment are established; O_i is set as the coordinate origin located within the center of wheels, and it is considered as the reference particle of the segment; Ν_i is the join point between the ith and the (i−1)th segment; d_i is the distance from Ν_i to O_i and e_i is the distance from Ν_{i + 1} to O_i; α is the steering angle of the first segment with the counterclockwise direction being deemed as positive; u is the translational velocity of the front wheel of the first segment; v_i is the translational velocity of the ith segment; V_Ni is the velocity of the ith segment; ω_i is the steering angular velocity of the ith segment; β_i is the angle between x_i-axis and X-axis, and ψ_i is the longitudinal axis angle between the ith and the (i + 1) th segments; and $(x_{i}, y_{i}, β_{i}) (i = 1, 2, 3)$ is the configuration description of each segment with three configuration parameters.

Establishment of the kinematics model

For the first segment, u, α and v₁, ω₁ are the control inputs and outputs of the system, respectively. According to the influence of nonholonomic constraints on the system motion and the geometrical relations among the kinematics parameters, the kinematics model between inputs and outputs is obtained as

[\begin{matrix} v_{1} \\ ω_{1} \end{matrix}] = [\begin{matrix} u cos α \\ \frac{sin α}{d_{1}} u \end{matrix}]

Meanwhile, the configuration parameters and velocity of the first segment are derived

[\begin{matrix} {\dot{x}}_{1} \\ {\dot{y}}_{1} \\ {\dot{β}}_{1} \end{matrix}] = [\begin{matrix} v_{1} cos β_{1} \\ v_{1} sin β_{1} \\ w_{1} \end{matrix}] = [\begin{matrix} cos β_{1} \\ sin β_{1} \\ \frac{tan α}{d_{1}} \end{matrix}] u cos α

In Figure 1, the relations of speed between the first and second segments can be expressed as

[\begin{matrix} v_{2} \\ ω_{2} \end{matrix}] = [\begin{matrix} v_{1} cos ψ_{1} + ω_{1} e_{1} sin ψ_{1} \\ \frac{v_{1}}{d_{2}} sin ψ_{1} - - \frac{ω_{1} e_{1}}{d_{2}} cos ψ_{1} \end{matrix}] = [\begin{matrix} cos ψ_{1} & e_{1} sin ψ_{1} \\ \frac{1}{d_{2}} sin ψ_{1} & - \frac{e_{1}}{d_{2}} cos ψ_{1} \end{matrix}] [\begin{matrix} v_{1} \\ ω_{1} \end{matrix}]

The relations of speed between the second and third segments can be deduced simultaneously as

[\begin{matrix} v_{3} \\ ω_{3} \end{matrix}] = [\begin{matrix} v_{2} cos ψ_{2} + ω_{2} e_{2} sin ψ_{2} \\ \frac{v_{2}}{d_{3}} sin ψ_{2} - - \frac{ω_{2} e_{2}}{d_{3}} cos ψ_{2} \end{matrix}] = [\begin{matrix} cos ψ_{2} & e_{2} sin ψ_{2} \\ \frac{1}{d_{3}} sin ψ_{2} & - \frac{e_{2}}{d_{3}} cos ψ_{2} \end{matrix}] [\begin{matrix} v_{2} \\ ω_{2} \end{matrix}] = [\begin{matrix} cos ψ_{2} & e_{2} sin ψ_{2} \\ \frac{1}{d_{3}} sin ψ_{2} & - \frac{e_{2}}{d_{3}} cos ψ_{2} \end{matrix}] [\begin{matrix} cos ψ_{1} & e_{1} sin ψ_{1} \\ \frac{1}{d_{2}} sin ψ_{1} & - \frac{e_{1}}{d_{2}} cos ψ_{1} \end{matrix}] [\begin{matrix} v_{1} \\ ω_{1} \end{matrix}]

The independent configuration parameters β₂ of the second segment and β₃ of the third segment can be expressed separately as

\begin{array}{l} {\dot{β}}_{2} = ω_{2} = \frac{v_{1}}{d_{2}} sin ψ_{1} - \frac{e_{1} ω_{1}}{d_{2}} cos ψ_{1} = \frac{1}{d_{2}} [(cos α sin β_{1} - \frac{e_{1}}{d_{1}} sin α cos β_{1}) cos β_{2} - (cos α cos β_{1} + \frac{e_{1}}{d_{1}} sin α sin β_{1}) sin β_{2}] u \\ = f_{2} (x) u \end{array}

\begin{array}{l} {\dot{β}}_{3} = ω_{3} = [\frac{sin ψ_{2} cos ψ_{1}}{d_{3}} - \frac{e_{2}}{d_{3} d_{2}} cos ψ_{2} sin ψ_{1}] v_{1} + [\frac{e_{1} {sin}^{2} ψ_{1}}{d_{3}} + \frac{e_{1} e_{2}}{d_{3} d_{2}} cos ψ_{1} cos ψ_{2}] ω_{1} \\ = \frac{1}{d_{3}} {\begin{cases} [cos α sin β_{1} - \frac{e_{1}}{d_{1}} sin α cos β_{1} - (d_{2} + e_{2}) cos β_{2} f_{2} (x)] cos β_{2} - \\ [cos α cos β_{1} - \frac{e_{1}}{d_{1}} sin α sin β_{1} - (d_{2} + e_{2}) sin β_{2} f_{2} (x)] sin β_{2} \end{cases}} u \\ = f_{3} (x) u \end{array}

The angles of the adjacent segments and turn angles of each segment satisfy the following relations

\begin{array}{l} {\dot{ψ}}_{1} = {\dot{β}}_{2} - {\dot{β}}_{1} = [f_{2} (x) - f_{1} (x)] \frac{v}{cos α} \\ {\dot{ψ}}_{2} = {\dot{β}}_{3} - {\dot{β}}_{2} = [f_{3} (x) - f_{2} (x)] \frac{v}{cos α} \end{array}

Accordingly, the kinematics equation of the system in matrix form is obtained as

[\begin{matrix} {\dot{x}}_{1} \\ {\dot{y}}_{1} \\ {\dot{β}}_{1} \\ ψ_{1} \\ ψ_{2} \end{matrix}] = [\begin{matrix} cos β_{1} \\ sin β_{1} \\ \frac{tan α}{d_{1}} \\ g_{1} (x) \\ g_{2} (x) \end{matrix}] u cos α

in which, g₁ (x) and g₂ (x) can be expressed as

{\begin{matrix} g_{1} (x) = - \frac{tan α}{d_{1}} - \frac{sin ψ_{1} + \frac{e_{1}}{d_{1}} cos ψ_{1} tan α}{d_{2}} \\ g_{2} (x) = [f_{3} (x) - f_{2} (x)] \frac{1}{cos α} \end{matrix}

Description and analysis of system trajectory

It is necessary to study the system trajectory to obtain a reasonable path planning for mobile articulated robots system. The trajectories of all segments are basically the same when the system reaches its destination in straight, while a set of trajectory family is produced because of the included angle between the segments when the system run along an arc to form a band path.^16,17 The width of band path determines the breadth of the system that ensures the safe operation. Therefore, the change rule of motion trajectories is described and analyzed accurately to plan an optimal and feasible path, rather than plan path by using the traditional method, namely considering the system as a particle directly.

The location coordinates of each segment wheels at any time can be obtained by equations (2), (5), and (6). Accordingly, the trajectories of each segment can be determined within its path range with a given tracking path of the first segment to determine the band path of the whole system. Suppose that the first segment tracks the path described as ${\begin{matrix} x = δ (t) \\ y = γ (t) \end{matrix}$ , then the trajectory of the left and right wheels of the ith segment can be calculated as

{\begin{matrix} α_{L i} (t) = δ_{i} (t) - \frac{d}{2} sin β_{i} \\ β_{L i} (t) = γ_{i} (t) + \frac{d}{2} cos β_{i} \end{matrix}; {\begin{matrix} α_{R i} (t) = δ_{i} (t) + \frac{d}{2} sin β_{i} \\ β_{R i} (t) = γ_{i} (t) - \frac{d}{2} cos β_{i} \end{matrix} (i = 1, 2, 3)

The movement trajectories of the reference nodes of the second and third segments can be expressed separately as

{\begin{matrix} x_{2} = δ_{2} (t) = δ_{1} (t) - (e_{1} cos β_{1} + d_{2} cos β_{2}) \\ y_{2} = γ_{2} (t) = γ_{1} (t) - (e_{1} sin β_{1} + d_{2} sin β_{2}) \end{matrix}

{\begin{matrix} x_{3} = δ_{3} (t) = δ_{1} (t) - (e_{1} cos β_{1} + e_{2} cos β_{2} + d_{2} cos β_{2} + d_{3} cos β_{3}) \\ y_{3} = γ_{3} (t) = γ_{1} (t) - (e_{1} sin β_{1} + e_{2} sin β_{2} + d_{2} sin β_{2} + d_{3} sin β_{3}) \end{matrix}

Choosing the configuration of the system when the first segment begins to follow a given curve as the initial condition, the configuration at any time instant can be solved from the nonlinear differential equations (2), (5), and (6) using Runge–Kutta method. Then the motion trajectories of the system are obtained after solving equations (10), (11), and (12) using numerical calculations, as presented in Figure 2.

Figure 2.

Band path of mobile articulated robots system with three segments.

Now that the trajectories are analyzed and the band path is described based on the kinematics model of the system with three segments. The configuration of the articulated segments can only be controlled by the inputs of the first segment¹⁸ and the articulated segments asymptotically track the trajectory of the first segment¹⁹ to provide theoretical support for the breadth of the system. A general path computed by planner can be approximated to a curve made up of straight segments connected with tangent circular arcs. Moreover, a straight line is equivalent to a circle with infinite radius. Thus, this article focuses on analyzing the feature of the motion paths when the tractor moves along a circle path. Assume that $e_{1} = e_{2} = e_{3} = e and d_{1} = d_{2} = d_{3} = d$ .

For the mobile articulated robots system linked with nonstandard form and d ≥ e, if the first segment follows the circle path with the minimum radius r₁, the motion paths of the second and third segments will exponentially converge to a set of concentric circles with radiuses $r_{i} = \sqrt{r_{i - 1}^{2} + e^{2} - d^{2}}, (i = 2, 3)$ . For the steady state shown in Figure 3, the band path is an annular-shaped band with the width is $W = r_{1} - r_{3} + D$ , in which D is the width of each segment.

Figure 3.

Band path when the system traces a circle.

Environment processing

Free-space method is one of the most frequently used motion planning algorithms focus on environment model and the corresponding path search strategy. To find a path free of collision between an initial position and a goal position, the free space for the dimensioned mobile articulated robots system, termed as its configuration space, is generated by shrinking the system to be a particle while correspondingly enlarging the obstacles of the environment according to the circumradius of the system or other suitable size. The circumradius is generally adopted to enlarge the obstacles for mobile robots with single segment. As far as mobile articulated robots system is concerned, the circumradius is relatively large, which would inevitably cause the loss of many feasible space. As a result, the robot might find a much longer path or even find no path in the environment. Moreover, the width of path is likely to be much less than the maximum extension size of the system because of the varying of circumradius and the theory of the articulated segments incremental tracking the first segment. Therefore, it is necessary to find a reasonable size to enlarge the obstacles.

There are extreme conditions in the utmost steering angles among the segments when the second and third segments follow the first one. It determines the maximum steering angle due to the nonholonomic constraint. Therefore, the minimum radius of the system running along an arc is determined and the width of the band path is the maximum now. ES is used to enlarge obstacles in static workspace so as to plan path effectively for this kind of robot.²⁰ $ES (x_{r}, x_{a})$ includes two parameters: the distance parameter x_r being the size for enlarging obstacles and the curvature parameter x_a being the minimum turning radius of system. The dimension x_r can be described by the maximum width of the band path when the system run along an arc with the minimum radius, as defined as $x_{r} = r_{min (1)} - r_{min (3)} + \frac{D}{2}$ in the case of d ≥ e and $x_{r} = r_{min (3)} - r_{min (1)} + \frac{D}{2}$ in the case of d ≤ e, in which $r_{min (i)} (i = 1, 2, 3)$ is the minimum turning radius of the ith segment. The dimension x_a is defined as the curvature of the arc, defined as $x_{a} = \frac{1}{r_{min (1)}}$ .

Accordingly, $ES (x_{r}, x_{a})$ are obtained according to the extreme conditions in the utmost steering angles, thus meeting with the nonholonomic constraint and ensuring the collision avoidance in path planning. If we use the dimension x_r to enlarge the obstacles, the system can be treated as a particle. The path planning for this particle is also feasible for the original mobile articulated robots system. Quantum computation of the $E S (x_{r}, x_{a})$ of the mobile articulated robots system with three segments connected by nonstandard form is as follows.²⁰

Case 1: d ≥ e

The turning radius of the segments from the first one to the last one reduces in turn, while the longitudinal axis angle between the ith and the (i+1)th segments increases in turn when the system run along an arc under the configuration of d ≥ e. The aforementioned relations can be explained as

R_{i} \geq r_{i} \geq r_{i + 1}, ψ_{i} \leq ψ_{i + 1} \begin{matrix} (i = 1, 2) \end{matrix}

The minimum turning radius of the third segment is derived as

r_{min (3)} = \frac{e + d cos ψ_{max}}{sin ψ_{max}}

in which ψ_max is the maximum longitudinal axis angle, and $ψ_{max} = ψ_{2}$ .

And the turning radius of the first segment can be deduced as

r_{min (1)} = \sqrt{r_{min (3)}^{2} + 2 (d^{2} - e^{2})}

The distance parameter x_r can be given by

x_{r} = r_{min (1)} - r_{min (3)} + \frac{D}{2} = \sqrt{r_{min (3)}^{2} + 2 (d^{2} - e^{2})} - r_{min (3)} + \frac{D}{2}

Case 2: d ≤ e

The turning radius of the segments from the first one to the last one increases in turn, while the longitudinal axis angle between the ith and the (i+1)th segments decreases in turn when the system run along an arc under the configuration of d ≤ e. The aforementioned relations can be explained as

R_{i} \leq r_{i} \leq r_{i + 1}, ψ_{i} \geq ψ_{i + 1} \begin{matrix} (i = 1, 2) \end{matrix}

The minimum turning radius of the first segment is derived as

r_{min (1)} = \frac{d + e cos ψ_{max}}{sin ψ_{max}}

in which ψ_max is the maximum longitudinal axis angle, and $ψ_{max} = ψ_{1}$ .

And the turning radius of the third segment can be deduced as

r_{min (3)} = \sqrt{r_{min (1)}^{2} + 2 (e^{2} - d^{2})}

The distance parameter x_r can be given by

x_{r} = r_{min (3)} - r_{min (1)} + \frac{D}{2} = \sqrt{r_{min (1)}^{2} + 2 (e^{2} - d^{2})} - r_{min (1)} + \frac{D}{2}

Both cases of d ≥ e and d ≤ e should be comprehensively considered for the system. x_r and x_a are expressed as

x_{r} = {\begin{matrix} \sqrt{{(\frac{e + d cos ψ_{max}}{sin ψ_{max}})}^{2} + 2 (d^{2} - e^{2})} - \frac{e + d cos ψ_{max}}{sin ψ_{max}} + \frac{D}{2}, d \geq e \\ \sqrt{{(\frac{d + e cos ψ_{max}}{sin ψ_{max}})}^{2} + 2 (d^{2} - e^{2})} - \frac{d + e cos ψ_{max}}{sin ψ_{max}} + \frac{D}{2}, d \leq e \end{matrix}

x_{a} = {\begin{array}{l} \frac{1}{\sqrt{{(\frac{e + d cos ψ_{max}}{sin ψ_{max}})}^{2} + 2 (d^{2} - e^{2})}}, d \geq e \\ \frac{sin ψ_{max}}{d + e cos ψ_{max}}, \begin{matrix} \begin{matrix} \begin{matrix}  \end{matrix} \end{matrix} \end{matrix} d \leq e \end{array}

Environmental models are obtained by enlarging obstacles when $d = \frac{e}{2}$ , as illustrated in Figure 4. The maximum extension size adopted as the obstacles enlarging size can make the feasible space be greatly lost, so that the quality of planning path reduces seriously and even make it impossible to discover an objective and feasible path (Figure 4). However, ES adopted as the obstacles enlarging size can preserve the feasible space as much as possible, so that it can be conducive to improve the efficiency of environment modeling and the success rates of path planning (Figure 4).

Figure 4.

Environment processing: (a) enlarging the obstacles by adopting the maximum extension size and (b) enlarging the obstacles by adopting ES. ES: equivalent size.

The improved A* algorithm is used to plan path for mobile articulated robots in free space. It can ensure itself as a collision-free and feasible path as long as the maximum path curvature is no larger than x_a.

Path planning based on the improved A* algorithm

Environment modeling

Path planning mainly includes several steps: environment modeling, path searching, and path smoothing. Three common methods of environment modeling are grid method, geometric method, and topological graph. Grid method was proposed by Elfes²¹ firstly. It has been widely applied, since it is easy to create and maintain. The overall environment is divided into several identically sized grids by adopting grid method, and then each grid should be indicated the presence of obstacles.

Mobile articulated robots system with three segments, recorded as ϒ, has shrunk to be a particle moving on two-dimensional plane. Several obstacles of the environment are mapped into hazardous areas that are refused to pass through. Δ is a convex polygon with limited and arbitrary shapes in the plane. There are several obstacles $Λ_{i} (i = 1, 2, \dots, n)$ distributed on the Δ. $Λ_{i} (i = 1, 2, \dots, n)$ with uncertain shapes are arbitrary denumerable and distributed randomly. Pad out Δ to regular rectangle. Besides, ϒ moves in the region of Δ and its initial goal positions are uncertain. Rasterized environmental information is mapped into plane coordinate system xoy. $Λ_{i} (i = 1, 2, \dots, n)$ in Δ and the supplement of Δ are converted into obstacle regions. Suppose that the step of ϒ in Δ is expressed as δ, and the maximum of Δ on x-axis and y-axis are represented as x_max and y_max, respectively. Therefore, the grid cells of Δ ranks are calculated as $n_{c} = x_{max} / δ and n_{l} = y_{max} / δ$ , respectively, as illustrated in Figure 5, in which g is recorded as arbitrary grid; Π is the set of grids in Δ; $g_{i} (x_{i}, y_{i})$ is the coordinate of g in Π; g(1,1) is the first grid in the lower left corner of the environment; the square is the initial position and the star is the goal position.

Figure 5.

Rasterizing environment of mobile articulated robots system with three segments.

$g_{t} (x_{t}, y_{t})$ is determined by the following formula

{\begin{matrix} x_{t} = ((i - 1) mod n_{c}) + 1 \\ y_{t} = (int) ((i - 1) / n_{c}) + 1 \end{matrix}

The improved A* algorithm

The system moves safely and collision-free from an arbitrary initial node S to an arbitrary goal node T along an optimal path on Δ to complete the path planning. The A* algorithm integrates Dijkstra algorithm closed to the initial node with Breadth-First Search (BFS) algorithm closed to the goal node. The goal positional information of the system is considered. The A* algorithm starts from S and updates the weight of subnodes of the current node in sequence and the current node by the minimum of the weight of subnodes until all the nodes are traversed or the current node is the goal node. Grid map and 8-connected nodes expanding method are adopted. The Euclidean distance from the current node t to the goal node T is considered as the heuristic function for the mobile articulated robots system, that is

h (t) = \sqrt{{(x_{t} - x_{T})}^{2} + {(y_{t} - y_{T})}^{2}}

The initial planning path, recorded as P_i, is obtained by calculation. In the path planning process of the system, the minimum node of the evaluation function f(t) adopted as an expanding node is deposited into CLOSE(C) list until expanding to the goal node. The flow chart of path planning for mobile articulated robots system based on the A* algorithm is shown in Figure 6, in which t is a node has been planned; g(t) is the actual movement distance from S to t; h(t) is the heuristic function, that is, the heuristic distance from t to T; f(t) is the path evaluation function of t, and $f (t) = g (t) + h (t); O P E N (O)$ is the queues collection for depositing the nodes waiting for extension and CLOSE(C) is the queues collection for depositing the nodes have been extended; f_e() is the function of extended node; f_i() is the function of inserted node, and the node is deposited into O in descending order of f(t). f_i() is executed and the node is inserted into O when the node is not the obstacle node or not be extended previously.

Figure 6.

Flow chart of path planning for mobile articulated robots system based on A* algorithm.

The improved A* algorithm is adopted to carry on the smoothing processing of the path to obtain the optimal planning path. All the nodes of the path are traversed based on the P_i. The path is extended and the middle node is deleted when there is no obstacle at the front and rear of the middle node, as illustrated in Figure 7, in which P* is the path planned by A* algorithm; SP* is the path planned by the improved A* algorithm; $P_{d} *$ is the number of nodes; d is the connect node; (d + 1) is the current node; (d + 2) is the next node of (d + 1); l_{d,d + 2} is the line between d and (d + 2). The arc is used to carry on the smoothing processing of corner to smooth the path, in which the maximum path curvature is no larger than x_a.

Figure 7.

Flow chart of path planning for mobile articulated robots system based on the improved A* algorithm.

Simulation results

The mobile articulated robots system with three segments moves in grid environments with obstacles distributed randomly. It is needed to verify the existence of obstacle between d and (d + 2) before connecting the two nodes. If it is yes, there is no passageway; otherwise it can be connected. It is easy to complete the path planning because the obstacles in the environment are arranged in neat array and the distance from the initial position to the goal position is short in Figure 8 and , while the obstacles with greater numbers in the environment are distributed randomly and the paths from the initial position to the goal position are more winding in Figure 8 and , in which the dotted line is the path planning obtained by the A* algorithm; the dashed line is the path planning obtained by the improved A* algorithm before the smoothing processing of corner; and the solid line is the path planning obtained by the improved A* algorithm after the smoothing processing of corner. The comparison of the planning paths between the A* algorithm (e.g. Figure 8 and ) and the improved A* algorithm (e.g. Figure 8 and ) shows that the quality of path by adopting the improved A* algorithm is superior to the A* algorithm no matter how complex the environment is.

There are a lot of problems in the planning path obtained by the A* algorithm as illustrated in Figure 8 and , such as many broken lines, turn times, and turn angles. The path is not what expected between the initial and goal positions in case of random distribution of obstacles.

The performance parameters of planning path obtained by the improved A* algorithm (e.g. Figure 8 and ) are superior to that of planning path obtained by the A* algorithm (e.g. Figure 8 and (c)) for mobile articulated robots system in case of random distribution of obstacles in a grid scale. For example, a 12.3% reduction in path length, a 25.3% reduction in accumulative turn times, and a 27.1% reduction in accumulative turn angles are obtained.

The improved A* algorithm makes the quality of path optimized and more suitable than the A* algorithm for path planning under the complex environment. The improved path meets the need of the optimal path planning for mobile articulated robots system seen from the above performance parameters.

Figure 8.

Comparison of paths planning: (a) path planning obtained by the A* algorithm in the simple environment, (b) path planning obtained by the improved A* algorithm in simple environment, (c) path planning obtained by the A* algorithm in the relatively complex environment, and (d) path planning obtained by the improved A* algorithm in the relatively complex environment.

Conclusion

A path planning method for mobile articulated robots system composed of three segments connected by nonstandard form based on the improved A* algorithm is proposed. The trajectories of each segment are analyzed and the band path is described based on the kinematics model of the system firstly; secondly, ES is introduced to enlarge obstacles in the environment to shrink the system to be a particle and ensures that the planning path is collision-free and feasible; thirdly, the improved A* Algorithm is elaborated; finally, path planning by the A* algorithm and the improved A* algorithm in the simple environment and in the relatively complex environment are simulated in Matlab. From the reduction rates of the path length, the accumulative turn times, and the accumulative turn angles, the proposed path planning method for mobile articulated robots system is collision-free and feasible.

Future studies mainly focus on two tasks: enlarging the number of segments to N and establishing the kinematics model; enhancing the diversification of the environment and improving the precision of environmental model.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

Khalaji

Moosavian

SAA

. Adaptive sliding mode control of a wheeled mobile robot towing a trailer. Proc Inst Mech Eng Part I J Syst Control Eng 2015; 229(2): 169–183. DOI: 10.1177/0959651814550539.

Khalaji

Moosavian

SAA

. Robust adaptive controller for a tractor–trailer mobile robot. IEEE/ASME Trans Mechatronics 2014; 19(3): 943–953. DOI: 10.1109/TMECH.2013.2261534.

Khalaji

Moosavian

SAA

. Modified transpose Jacobian control of a tractor-trailer wheeled robot. J Mech Sci Technol 2015; 29(9): 3961–3969. DOI: 10.1007/s12206-015-0841-3

Corke

Ridley

. Steering kinematics for a center-articulated mobile robot. IEEE Trans Robot Autom 2001; 17(2): 215–218. DOI: 10.1109/70.928568

Werling

Reinisch

Heidingsfeld

. Reversing the general one-trailer system: asymptotic curvature stabilization and path tracking. IEEE Trans Intell Transport Syst 2014; 15(2): 627–636. DOI: 10.1109/TITS.2013.2285602.

Astolfi

Bolzern

Locatelli

. Path-tracking of a tractor-trailer segment along rectilinear and circular paths: a Lyapunov-based approach. IEEE Trans Robot Autom 2004; 20(1): 154–160. DOI: 10.1109/TRA.2003.820928.

Kayacan

Ramon

. Distributed nonlinear model predictive control of an autonomous tractor–trailer system. Mechatronics 2014; 24(8): 926–933. DOI: 10.1016/j.mechatronics.2014.03.007.

Michałek

Kiełczewski

Jedwabny

. Cascaded VFO control for non-standard N-trailer robots. J Intell Robot Syst 2013; 77(3–4): 415–432. DOI: 10.1007/s10846-013-9881-z.

Michałek

. Lining-up control strategies for N-trailer segments. J Intell Robot Syst 2014; 75(1): 29–52. DOI: 10.1007/s10846-013-9846-2.

10.

Nayl

Nikolakopoulos

Gustafsson

. Effect of kinematic parameters on MPC based on-line motion planning for an articulated segment. Robot Autonom Syst 2015; 70: 16–24. DOI: 10.1016/j.robot.2015.04.005.

11.

Lamiraux

Sekhavat

Laumond

. Motion planning and control for Hilare pulling a trailer. IEEE Trans Robot Autom 1999; 15(4): 640–652. DOI: 10.1109/70.781968.

12.

Carlos

CDW

Ndoudi-Likoho

Micaelli

. Nonlinear control for a train-like segment. Int J Robot Res 1997; 16(3): 300–319. DOI: 10.1177/027836499701600303.

13.

Hart

Nilsson

Raphael

. A formal basis for the heuristic determination of minimum cost paths. Syst Sci Cybern IEEE Trans 1968; 4(2): 100–107. DOI: 10.1109/TSSC.1968.300136.

14.

Huang

Wang

. A novel hybrid method for mobile robot path planning in unknown dynamic environment based on hybrid DSm model grid map. J Exp Theor Artif Intell 2011; 23(1): 5–22. DOI: 10.1080/0952813X.2010.506283.

15.

Trovato

Dorst

. Differential A*. IEEE Trans Knowl Data Eng 2002; 14(6): 1218–1229. DOI: 10.1109/TKDE.2002.1047763.

16.

Zhang

Lapierre

Xiang

. Distributed control of coordinated path tracking for networked nonholonomic mobile segments. IEEE Trans Ind Inf 2013; 9(1): 472–484. DOI: 10.1109/TII.2012.2219541.

17.

Vatcha

Xiao

. Detection of robustly collision-free trajectories in unpredictable environments in real-time. Auton Robot 2014; 37(1): 81–96. DOI: 10.1007/s10514-013-9377-5.

18.

Matsushita

Murakami

. Nonholonomic equivalent disturbance based backward motion control of tractor-trailer with virtual steering. IEEE Trans Ind Electron 2008; 55(1): 280–287. DOI: 10.1109/TIE.2007.908522.

19.

Yuan

Sun

Huang

. Trajectory generation and tracking control for double-steering tractor–trailer mobile robots with on-axle hitching. IEEE Trans Ind Electron 2015; 62(12): 7665–7677. DOI: 10.1109/TIE.2015.2455016.

20.

Que

Huang

. Concept of equivalent size for tractor-trailer mobile robots and its application to path planning. In: Intelligent control and automation proceedings of world congress on, Shanghai, China, 10–14 June 2002, Vol. 2, pp.1143–1147. DOI: 10.1109/ WCICA.2002.1020758.

21.

Elfes

. Sonar based real-world mapping navigation. IEEE J Robot Autom 1987; 3(3): 249–265. DOI: 10.1109/JRA.1987.1087096.