Sage Journals: Discover world-class research

Abstract

This paper conducts research on collision and obstacle avoidance of multi-agent systems without mapping ability, while the constrained agent can only detect obstacles within a limited distance, then a velocity programing strategy is proposed considering the lack of a high-resolution map and the challenge of the modeling of complex obstacles. Based on the detecting information of nearby members and obstacles, a discontinuous velocity programing space is constructed by imposing the constraints on the velocity. To obtain expansive programing space, two different ways are utilized to establish the velocity constraints of avoiding various obstacles. For obstacles that can be viewed as virtual circular obstacles, a barrier function is introduced to restrict the radial component of the velocity. As for the obstacle that can only be detected partially, we use the border lines to construct a velocity feasible domain, and the domain is approximated by the polygonal region using the convex theory. Then, the nominal velocity is utilized as the objective and a nonlinear dynamic programing regulator is proposed. Furtherly, velocity limits generated from the system kinematic constraints are incorporated into the regulator. Finally, three tests are carried out and the feasibility of the proposed regulator is verified.

Keywords

Obstacle avoidance barrier function system kinematic constraints nonlinear dynamic programing multi-agent system

Introduction

Motion control for multi-agent systems is still a hot topic, and obstacle avoidance is critical and difficult in complex circumstances.^1,2 Without loss of generality, we view collision avoidance as internal obstacle avoidance. Research on obstacle avoidance previously mainly focused on path planning, analytical law designing, and dynamic programing.

The heuristic algorithms^3–7 are typical for path planning methods, which will provide globally optimal paths for agents. Considering the lack of dynamic constraints, intelligent algorithms,⁸ points selecting,⁵ cost function revision,⁶ and the Bessel curve and Dubins curve^9–12 are used to smooth the paths. However, those static algorithms require high-resolution maps and can only provide one path for a single agent, which is not applicable for multi-agent systems.

Differing from path optimizing, the artificial potential field (APF) focuses on acceleration control with various forces. Traditional APF requires that obstacles can be viewed as virtual circular obstacles (VCOs).¹ As for obstacles with complex boundaries,² applies the panel method for potential field design, but the mathematical model requires full information about obstacles. Besides, some system constraints are ignored. In terms of the angular rate constraint, Song et al.¹³ proposes a speed segmental adjustment strategy for field design, but it provides no methods for processing complex obstacles. Instead of field designing for each obstacle, global field functions have attracted much attention. Harmonic functions^14–17 can help avoid local traps, but they cannot be incorporated with dynamic constraints due to fixed forms. Homeomorphism transform gives flexible ways for constructing global filed.^18–23 The homeomorphism transform can stretch or compress irregular obstacles to VCOs or point obstacles, but the demand for full information about obstacles hinders the use of this method in complex circumstances.

Similar to APF, the interference field (IF) technology^24–27 control the velocity with a coefficient matrix, which will be updated by referring to the IF function at each point. Hence, the radial component of the relative velocity is restricted, and obstacle avoidance is realized. However, geometric models of obstacles are required for building IF, and maps containing full information about obstacles are demanded. Although memory storage and segment¹ can help the robot escape the unknown asymmetric trap, the segment will be complex facing multiple obstacles, and agents might fall into traps created by the bucking effect. Apart from the above methods, velocity planning^28–30 is also applied to void obstacles.²⁹ uses the tangent lines as the velocity guidance,³⁰ proposes the dynamic circular boundary for velocity planning. Despite those results, research about velocity planning still focuses on VCOs with fewer constraints. Recently, deep learning algorithms^31,32 are surveyed for obstacle avoidance, but networks need plentiful practical data for training.

Based on the above analysis, complex obstacle avoidance is still a challenge. Since complex obstacles have long and complex boundaries, VCOs’ processing will compress motion space for agents, the worst situation is that VCOs might intersect with each other and no feasible space is available. Besides, limited detection cannot provide full information about obstacles, which cannot be solved well with existing methods. Thus, avoiding complex obstacles without modeling obstacles deserves to be surveyed. In this paper, the dynamic programing (DP) method^33–35 is introduced to plan the velocity of agents. Multistep prediction³⁶ performs well for consensus control, but the boundaries of the obstacles might be time-varying due to limited detection. With the DP method, motion control can be treated as velocity programing, and obstacle avoidances can be viewed as velocity constraints. Differing the regulator designed for collision avoidance among robots,³³ nonlinear constraints will be built for complex obstacles and a nonlinear dynamic programing (NDP) regulator will be created in this paper. The velocity requirements for obstacle avoidance will be converted to various constraints of the regulator. For the sake of concise, we introduce the concept of rounded obstacles and non-rounded obstacles. Rounded obstacles represent obstacles that can be viewed as VCOs, and non-rounded obstacles are obstacles having complex boundaries and large areas. Internal agents causing interferences can be viewed as rounded obstacles. As for rounded obstacle avoidance, the velocity of the agent is planned by revising the radial component of the relative component. As for non-rounded obstacles, a feasible domain is defined and approximated with the convex hull algorithm for velocity planning. Firstly, the accessible relative velocity space is expressed as a circular domain with the radius being the maximum value of the relative velocity. Then, a convex hull can be created by rotating the border lines related to the boundaries of detected parts of non-rounded obstacles. The convex hull must cover the velocity space. Next, a polygonal feasible domain for velocity planning can be obtained by removing the infeasible parts. Based on the convex theories,³⁷ velocity constraints for non-rounded obstacle avoidance are built. The regulator with the above constraints can offer robust feasible solutions for agents. Although the regulator provides no analytical solutions due to nonlinear complex constraints, it shall offer feasible solutions and doesn’t need mathematical models of non-rounded obstacles, which will release the demand for full information about obstacles. Moreover, extra constraints can be added to the regulator in different environments.

The contributions of the paper can be summarized as follows: (1) A velocity programing strategy is proposed for collision and obstacle avoidance. Compared with the statistic heuristic algorithms, the proposed regulator does not need a high-resolution map and can provide feasible velocity when agents can only obtain local information about the environment; (2) A concise way is proposed to establish the velocity constraints for obstacles that cannot be detected wholly. By using the border lines and the convex theory, a feasible velocity space is constructed for complex obstacles, thus the challenge of modeling the complex obstacles that exist in the analytical law searching methods is avoided; (3) The system constraints can easily be incorporated into the regulator, while the statistic heuristic algorithms and the analytical law searching methods can easily encounter the input saturation.

The rest of the paper is organized as follows. Section 1 describes the problem of obstacle avoidance. Then, Section 2 gives the various velocity constraints of the programing model, and the programing regulator is proposed in Section 3. The simulation is conducted in Section 4, and Section 5 is the conclusion.

Notations: ${(*)}^{T}$ indicates the transpose of a vector or a matrix; ${*}_{i = 1}^{n}$ denotes the set owing $n$ elements; ‖*‖ is the Euclidean norm; $R^{+}$ denotes the set of positive real numbers; $R^{m \times n}$ indicates the set of real matrices with $m$ rows and $n$ columns.

Obstacle avoidance

Assuming there exist $n$ agents and $m$ obstacles in the environment. The states of agents at the time $t$ are defined as ${(p_{a}^{i} (t), v_{a}^{i} (t))}_{i = 1}^{n}$ with $p_{a}^{i} (t)$ being the positions and $v_{a}^{i} (t)$ being the velocity. Similarly, the states of the obstacles at the time $t$ are indicated as ${(p_{o}^{j} (t), v_{o}^{j} (t))}_{j = 1}^{m}$ with $p_{o}^{j} (t)$ being the positions and $v_{o}^{j} (t)$ being the velocity. The goals at the time $t$ are ${q_{a}^{i} (t), v_{d}^{i} (t)}_{i = 1}^{n}$ , where $q_{a}^{i} (t)$ indicates the desired position, $v_{d}^{i} (t)$ denotes the expected velocity.

Defining the nominal velocity at the time $t + 1$ as ${\bar{v}}_{a}^{i} (t + 1)$ , which satisfies the equality $f_{v} ({\bar{v}}_{a}^{i} (t + 1), p_{r}^{ij} (t), v_{r}^{ij} (t), p_{r}^{i} (t), v_{r}^{i} (t)) = 0$ , where $f_{v} (*)$ is the control law, $p_{r}^{ij} (t) = p_{o}^{j} (t) - p_{a}^{i} (t)$ , $v_{r}^{ij} (t) = v_{a}^{i} (t) - v_{o}^{j} (t)$ , $p_{r}^{i} (t) = p_{a}^{i} (t) - q_{a}^{i} (t)$ , and $v_{r}^{i} (t) = v_{a}^{i} (t) - v_{d}^{i} (t)$ .

Considering the difficulty in designing analytical solutions, the re-planning strategy³⁴ is introduced to build an NDP regulator for obstacle avoidance. Taking the nominal velocity ${\bar{v}}_{a}^{i} (t + 1)$ as the reference, the regulator will reoptimize the velocity under a series of constraints and provide a revised value $v_{a}^{i} (t + 1)$ for agents. The strategy can be indicated as:

{\begin{matrix} f_{v} ({\bar{v}}_{a}^{i} (t + 1), p_{r}^{ij} (t), v_{r}^{ij} (t), p_{r}^{i} (t), v_{r}^{i} (t)) = 0 \\ f (v_{a}^{i} (t + 1), p_{r}^{ij} (t), v_{r}^{ij} (t)) \leq 0 \\ g (v_{a}^{i} (t + 1), v_{a}^{i} (t), v_{m}^{i}, ω_{m}^{i}) \leq 0 \end{matrix}

(1)

Where $v_{m}^{i}$ and $ω_{m}^{i}$ indicate the maximum velocity and the maximum angular rate respectively. $f (*)$ represents the demand for obstacle avoidance, and $g (*)$ indicates the system constraints.

The objective function is given below:

J = \frac{1}{2} {(v_{a}^{t + 1} - {\bar{v}}_{a}^{t + 1})}^{T} R (v_{a}^{t + 1} - {\bar{v}}_{a}^{t + 1})

(2)

Where $v_{a}^{t + 1} = {[{(v_{a}^{1} (t + 1))}^{T}, \dots, {(v_{a}^{n} (t + 1))}^{T}]}^{T}$ , ${\bar{v}}_{a}^{t + 1} = {[{({\bar{v}}_{a}^{1} (t + 1))}^{T}, \dots, {({\bar{v}}_{a}^{n} (t + 1))}^{T}]}^{T}$ , and $R$ is the non-negative symmetric definite matrix.

Then, the NDP regulator can be expressed as:

\begin{array}{l} J = \frac{1}{2} {(v_{a}^{t + 1} - {\bar{v}}_{a}^{t + 1})}^{T} R (v_{a}^{t + 1} - {\bar{v}}_{a}^{t + 1}) \\ s . t . \\ f (v_{a}^{t + 1} (t + 1), p_{r}^{i j} (t), v_{r}^{i j} (t)) \leq 0 \\ g (v_{a}^{t + 1} (t + 1), v_{a}^{i} (t), v_{m}^{i}, ω_{m}^{i}) \leq 0 \end{array}

(3)

Defining $m_{i}$ obstacles interfering agent $i$ at the time $t$ as ${(p_{o}^{i_{k}} (t), v_{o}^{i_{k}} (t))}_{k = 1}^{m_{i}}$ , where $1 \leq i_{k}, m_{i} \leq m$ . Then we can get $p_{r}^{i i_{k}} (t) = p_{r}^{i_{k}} (t)$ and $v_{r}^{i i_{k}} (t) = v_{r}^{i_{k}} (t)$ , equation (3) can be rewritten as:

\begin{array}{l} J = \frac{1}{2} {(v_{a}^{t + 1} - {\bar{v}}_{a}^{t + 1})}^{T} R (v_{a}^{t + 1} - {\bar{v}}_{a}^{t + 1}) \\ s . t . \\ f (v_{a}^{t + 1}, {\tilde{p}}_{r} (t), {\tilde{v}}_{r} (t)) \leq 0 \\ g (v_{a}^{t + 1}, v_{a}^{t}, v_{m}, ω_{m}) \leq 0 \end{array}

(4)

Where $v_{m} = {[v_{m}^{1}, \dots, v_{m}^{n}]}^{T}$ , $ω_{m} = {[ω_{m}^{1}, \dots, ω_{m}^{n}]}^{T}$ , ${\tilde{p}}_{r} (t)$ and ${\tilde{v}}_{r} (t)$ are indicated as:

\begin{matrix} {\tilde{p}}_{r} (t) = {[\underset{m_{1}}{\underset{︸}{p_{r}^{1_{1}} (t), \dots, p_{r}^{1_{m_{1}}} (t)}}, \underset{m_{1}}{\underset{︸}{p_{r}^{2_{1}} (t), \dots, p_{r}^{2_{m_{1}}} (t)}}, \dots, \underset{m_{1}}{\underset{︸}{p_{r}^{n_{1}} (t), \dots, p_{r}^{n_{m_{1}}} (t)}}]}^{T} \\ {\tilde{v}}_{r} (t) = {[\underset{m_{1}}{\underset{︸}{v_{r}^{1_{1}} (t), \dots, v_{r}^{1_{m_{1}}} (t)}}, \underset{m_{1}}{\underset{︸}{v_{r}^{2_{1}} (t), \dots, v_{r}^{2_{m_{1}}} (t)}}, \dots, \underset{m_{1}}{\underset{︸}{v_{r}^{n_{1}} (t), \dots, v_{r}^{n_{m_{1}}} (t)}}]}^{T} \end{matrix}

Without velocity reference, the equation (4) can be revised as:

\begin{matrix} J = \frac{1}{2} {(p_{a}^{t + 1} - q_{a}^{t + 1})}^{T} Q (p_{a}^{t + 1} - q_{a}^{t + 1}) \\ + \frac{1}{2} {(v_{a}^{t + 1})}^{T} {Rv}_{a}^{t + 1} \\ s . t . \\ p_{a}^{t + 1} = {Ap}_{a}^{t} + {Bv}_{a}^{t} \\ f (v_{a}^{t + 1}, {\tilde{p}}_{r} (t), {\tilde{v}}_{r} (t)) \leq 0 \\ g (v_{a}^{t + 1}, v_{a}^{t}, v_{m}, ω_{m}) \leq 0 \end{matrix}

(5)

Where $Q$ is the non-negative symmetric definite matrix, $A$ and $B$ are state transition matrices. $p_{a}^{t}$ and are $q_{a}^{t}$ indicated as:

\begin{matrix} p_{a}^{t} = {[{(p_{a}^{1} (t))}^{T}, \dots, {(p_{a}^{n} (t))}^{T}]}^{T}; \\ q_{a}^{t} = {[{(q_{a}^{1} (t))}^{T}, \dots, {(q_{a}^{n} (t))}^{T}]}^{T} \end{matrix}

Whatever the objective, the design of constraints $f (\cdot)$ is crucial and difficult.

Constraints of the regulator

In this section, we discuss various constraints for obstacle avoidance in different situations.

Rounded obstacles

The coordinate used in this paper is the inertial reference frame $xoy$ shown in Figure 1. As depicted in Figure 1, rounded obstacles could be processed as separate VCOs denoted as circular blue circles. Distances among VCOs satisfy some restrictions mentioned in many papers,^21,23 otherwise, VCOs with small distances should be combined as a bigger virtual circular obstacle (VCO). Boundaries of VCOs should not be penetrated for rounded obstacles. Thus, the radial component of the relative velocity must be zero or point outside the circle, such as the red lines with arrows along the feasible path indicated as the black dotted line in Figure 1.

Figure 1.

Rounded obstacles avoidance.

Based on the above analysis, the demand for rounded obstacles avoidance discussed above can be expressed with the following constraints:

\begin{matrix} {(v_{r}^{i_{k}} (t + 1))}^{T} p_{r}^{i_{k}} (t) \leq 0, p_{r}^{i_{k}} (t) = R_{i_{k}} \end{matrix}

(6)

Where $R_{i_{k}}$ indicate the radius of the VCO.

Equation (6) cannot be directly used as the velocity constraints considering the following two factors: (1) The control is not smooth if the constraint (6) is imposed on the velocity instantaneously due to the condition $p_{r}^{i_{k}} (t) = R_{i_{k}}$ ; (2) The instantaneous demand might not be able to be realized for constrained agents.³⁸ Motivating by Wang et al.,³³ a barrier function is introduced for velocity programing in this paper. Then we can have Theorem 1.

Theorem 1: For the rounded obstacle $i_{k}$ , agent $i$ could avoid it if the relative velocity satisfies the inequality (7).

\begin{matrix} \begin{matrix} {(v_{r}^{i_{k}} (t + 1))}^{T} p_{r}^{i_{k}} (t) \\ \leq (‖ p_{r}^{i_{k}} (t) ‖ - R_{i_{k}}) v_{m}^{i} \end{matrix} \end{matrix}

(7)

Proof: The agent is expected to maintain a safe distance from the obstacle. To achieve the purpose, the programing velocity should make the agent always stay in a safe region. Using a barrier function $h (p_{i} (t)) = ‖ p_{r}^{i_{k}} (t) ‖ - R_{i_{k}}$ , the safe region can be denoted as the position set $ℓ = {p_{i} (t) | h (p_{i} (t)) \geq 0}$ . The Wang et al.³³ has proved that obstacle avoidance can be realized if the barrier function $h (p_{i} (t))$ satisfies (1) the barrier function is derivable and (2) the derivative of the barrier function satisfies the inequality $\overset{\cdot}{h} (p_{i} (t)) + κ (h (p_{i} (t))) \geq 0$ with $κ$ being an extended class- $K$ function in the section $(- b, a) \to R$ for some $a, b > 0$ .³³ Taking the derivative of $h (p_{i} (t))$ and using the class- $K$ function $κ (h (p_{i} (t))) = (‖ p_{r}^{i_{k}} (t) ‖ - R_{i_{k}}) v_{m}^{i}$ , we can incorporate the condition in the velocity constraint (7), which means the velocity constraint (7) can help realize obstacle avoidance. We can explain (7) explicitly by analyzing the radial component with the velocity constraint (7). Dividing both sides by $p_{r}^{i_{k}} (t)$ and we can get:

\begin{matrix} \begin{matrix} {(v_{r}^{i_{k}} (t + 1))}^{T} p_{r}^{i_{k}} (t) / ‖ p_{r}^{i_{k}} (t) ‖ \\ \leq (1 - R_{i_{k}} / ‖ p_{r}^{i_{k}} (t) ‖) v_{m}^{i} \end{matrix} \end{matrix}

(8)

The left side of the inequality in (8) represents the radial component of the relative velocity. Since we have $p_{r}^{i_{k}} (t) - R_{i_{k}} = 0$ at the boundary of the domain, the demand is satisfied and agent $i$ can avoid obstacle $i_{k}$ .

Non-rounded obstacles

Non-rounded obstacles cannot be viewed as VCOs, as the radius of the VCO related to a non-rounded obstacle might be big enough to compress velocity planning space, such as roadside, the canyon, and riverbank. Thus, the regulator might have no feasible solutions. The segmentation method has been used in Wu et al.¹ for non-rounded obstacle processing, but fields aroused from discrete VCOs might counteract at some positions, which will cause traps. Instead of dividing non-rounded obstacles, the strategy of designing a feasible domain for velocity is proposed in this paper.

As seen in Figure 2, the relative velocity of the agent should not point to the obstacle for obstacle avoidance, which can be realized by constructing an exclusive space for unexpected relative velocity. The exclusive space might be created with tangential lines to the obstacle, such as gray parts sandwiched by dotted blue border lines in Figure 2. However, a complete exclusive velocity space contains more than a sector due to system constraints, namely maximum velocity and angular rate limitations. Therefore, using exclusive space to establish constraints is difficult. Instead, a feasible domain for relative velocity will be created, with which the agent can avoid the obstacles. For the construction of the feasible domain, the convex hull algorithm will be applied here.

Figure 2.

Velocity requirements for non-rounded obstacles avoidance.

Defining border lines as $(l_{i_{k}}^{1} (t), l_{i_{k}}^{2} (t))$ , of which the normal vectors are indicated as $(n_{i_{k}}^{1} (t), n_{i_{k}}^{2} (t))$ . Then, a new coordinate frame $o_{n} x_{n} y_{n}$ fixed in the agent is introduced with $(n_{i_{k}}^{1} (t), n_{i_{k}}^{2} (t))$ , and the axes are parallel to the vectors $(n_{i_{k}}^{1} (t), n_{i_{k}}^{2} (t))$ . For the point $p$ in $xoy$ , its new coordinate in $o_{n} x_{n} y_{n}$ can be indicated as $(p^{T} n_{i_{k}}^{1} (t), p^{T} n_{i_{k}}^{2} (t))$ .

Since $p^{T} n_{i_{k}}^{1} (t)$ is negative on one side of $l_{i_{k}}^{1} (t)$ and positive on the other side, and $p^{T} n_{i_{k}}^{2} (t)$ has the same characteristic as $p^{T} n_{i_{k}}^{1} (t)$ , border lines can be used to divide the whole space into four boundless sectors. But boundless sectors are insufficient for constructing the feasible domain.

In this paper, polygons fenced with lines are applied for constructing bounded domains, such as the hexagonal domain $O A_{1} A_{2} A_{3} A_{4} A_{5} A_{6}$ in Figure 3. Labeling the vertexes as ${O, A_{1}, A_{2}, \dots, A_{l}, \dots, A_{N}}$ with $N$ being the number of edges and $O$ being located at agent $i$ . Thus, the lines required can be indicated with a series of vectors: $\vec{O A_{1}} = l_{1} (i_{k}, t)$ ; $\vec{A_{l - 1} A_{l}} = l_{l} (i_{k}, t)$ ; $\vec{A_{N} O} = l_{N + 1} (i_{k}, t)$ , $2 \leq l \leq N$ . The positions are indicated as ${p_{t}^{1}, p_{t}^{2}, \dots, p_{t}^{l}, \dots, p_{t}^{N}}$ , then we have Theorem 2.

Theorem 2: There exists a minimum positive integer value $N_{ε}$ , and for any $N \geq N_{ε} + 1$ , agent $i$ can avoid obstacles with relative velocity in the domain $O A_{1} A_{2} \dots A_{N}$ under maximum value constraints.

Figure 3.

The polygonal domain with $N = 6$ .

Proof: We will finish the proof in three steps, in step one, a geometric expression of the feasible domain will be given. The way of constructing polygons will be described in step two. Thirdly, the minimum value $N_{ε}$ will be discussed.

Considering that the velocity of obstacles is restricted, we have $v_{o}^{j} (t) \leq a$ , where $a \in R^{+}$ indicates the maximum velocity of obstacles. Therefore, the relative velocity is bounded by $v_{r}^{i_{k}} \leq b$ , where $b \in R^{+}$ is a positive real number. Thus, the relative velocity space can be expressed as a circular domain (the red circle in Figure 4) with $b$ being the radius, and a convex hull with vertexes ${A_{1}, A_{2} \dots, A_{l}, \dots, A_{N}}$ can be used to represent the whole velocity space under maximum value constraints. Removing the exclusive space, we can get the polygons $O A_{1} A_{2} \dots A_{N}$ containing the feasible domain with $θ = π - ∠ A_{1} O A_{2}$ being the radial angle.

Figure 4.

Construction of the polygonal domain with $N = 5$ .

By dividing the feasible domain into $N - 1$ parts, we can get $N - 1$ arcs whose radial angles satisfy the limits $θ / (N - 1) < π$ and $θ / (N - 2) \geq π$ . Then, we can choose points on arcs freely and get the tangent located at these points, with which the polygons can be constructed, such as the hexagon $O A_{1} A_{2} A_{3} A_{4} A_{5}$ in Figure 4.

It should be stated that the number of constraints will increase with increasing $N$ . So, it is crucial to get a minimum $N$ for reducing the time cost. Based on the above analysis, one sector is enough if $θ < π$ . But if $θ \geq π$ , the feasible domain should be divided into at least two parts. Therefore, we have $N_{ε} = 2$ $θ \geq π$ when and $N_{ε} = 1$ when $θ < π$ . Thus Theorem 2 is proved.

Choosing $O A_{l} \equiv c$ with $c$ being the length satisfying $c \geq b$ , ${p_{t}^{1}, p_{t}^{2}, \dots, p_{t}^{l}, \dots, p_{t}^{N}}$ can be obtained based on Theorem 2.

Firstly, the positions of ${A_{1}, A_{N}}$ are given below:

{\begin{matrix} p_{t}^{1} = c l_{i_{k}}^{1} (t) / ‖ l_{i_{k}}^{1} (t) ‖ + p_{a}^{i} (t) \\ p_{t}^{N} = c l_{i_{k}}^{2} (t) / ‖ l_{i_{k}}^{2} (t) ‖ + p_{a}^{i} (t) \end{matrix}

(9)

Then, the positions of other vertexes can be computed with the following equation:

\begin{matrix} p_{t}^{l} = T (\frac{(l - 1) θ}{N - 1}) \end{matrix} (p_{t}^{1} - p_{a}^{i} (t)) + p_{a}^{i} (t)

(10)

Where $T (*)$ represents the rotating function.

Based on equations (9) and (10), the constraints are given with Theorem 3.

Theorem 3: For relative velocity $v_{r}^{i_{k}} (t + 1)$ in the feasible domain, there must exist a group of rotation matrices ${P_{1}, P_{2}, \dots, P_{l}, \dots, P_{N + 1}}$ with which the inequality (11) holds, and the value of $P_{l}$ is choose among ${[\begin{matrix} 0 - 1 \\ 10 \end{matrix}], [\begin{matrix} 01 \\ - 10 \end{matrix}]}$ .

{\begin{matrix} {(v_{r}^{i_{k}} (t + 1) + p_{a}^{i} (t) - p_{t}^{l - 1})}^{T} P_{l} l_{l} (i_{k}, t) \leq 0 \\ {(v_{r}^{i_{k}} (t + 1))}^{T} P_{1} l_{1} (i_{k}, t) \leq 0 \end{matrix}

(11)

Proof: Firstly, we have:

{(l_{l} (i_{k}, t))}^{T} P_{l} l_{l} (i_{k}, t) = 0

(12)

Referring to (12), the line $A_{l - 1} A_{l}$ can be represented as:

{(p - p_{t}^{l - 1})}^{T} P_{l} l_{l} (i_{k}, t) = 0

(13)

Where $p$ is any point on the line $A_{l - 1} A_{l}$ .

According to the definition, $v_{r}^{i_{k}} (t + 1) + p_{a}^{i} (t)$ must be in the feasible domain, which means the following inequalities hold with $P_{l} \in {[\begin{matrix} 0 - 1 \\ 10 \end{matrix}], [\begin{matrix} 01 \\ - 10 \end{matrix}]}$ based on the convex theory³⁷:

{(v_{r}^{i_{k}} (t + 1) + p_{a}^{i} (t) - p_{t}^{l - 1})}^{T} P_{l} l_{l} (i_{k}, t) \leq 0

(14)

Where $2 \leq l \leq N$ .

Since $p_{t}^{1}$ and $p_{a}^{i} (t)$ are zero vectors, we have ${(v_{r}^{i_{k}} (t + 1))}^{T} P_{1} l_{1} (i_{k}, t) \leq 0$ . The proof is finished.

Referring to Theorem 2 and Theorem 3, velocity constraints for non-rounded obstacles avoidance are given below:

\begin{matrix} P_{t} (rep (v_{r}^{i_{k}} (t + 1) + p_{a}^{i} (t)) - p_{t}) \leq 0 \end{matrix}

(15)

Where $rep (*)$ is the dimensional extension function related to the operational object $p_{t}$ . Matrices $P_{t} \in R^{(N + 1) \times 2 (N + 1)}$ and $p_{t} \in R^{2 (N + 1) \times (N + 1)}$ are:

{\begin{matrix} P_{t} = [\begin{matrix} P_{1} l_{1} (i_{k}, t) \dots 0 \\ ⋮ ⋱ ⋮ \\ 0 \dots P_{N + 1} l_{N + 1} (i_{k}, t) \end{matrix}] \\ p_{t} = [\begin{matrix} p_{t}^{1} \dots 0 \\ ⋮ ⋱ ⋮ \\ 0 \dots p_{t}^{N + 1} \end{matrix}] \end{matrix}

Compared with analytic solutions, NDP with inequality constraint in (13) is more robust.

Rigid constraints

In practice, the feasible domain in section 2.2 can be minimized considering that the backward movement of agents is not expected. Hence, the earthy yellow domain in Figure 3 should be removed and rigid constraints will be created. Next, we give rigid constraints with Theorem 4.

Theorem 4: For any point $B_{1}$ with the positions being indicated as $p_{t}^{B}$ in the gray part in Figure 3 and its symmetrical point in the earthy yellow domain, inequality (16) will always hold, where the constraint matrix $M_{t}^{i_{k}}$ is given by $M_{t}^{i_{k}} = P_{1} l_{i_{k}}^{1} (t) {(P_{2} l_{i_{k}}^{2} (t))}^{T}$ .

{(p_{t}^{B} - p_{a}^{i} (t))}^{T} M_{t}^{i_{k}} (p_{t}^{B} - p_{a}^{i} (t)) > 0

(16)

Proof: Referring to Theorem 3, we can get (17) if $p_{t}^{B}$ is not on the lines $(l_{i_{k}}^{1} (t), l_{i_{k}}^{2} (t))$ :

{\begin{matrix} {(p_{t}^{B} - p_{a}^{i} (t))}^{T} P_{1} l_{i_{k}}^{1} (t) > 0 \\ {(p_{t}^{B} - p_{a}^{i} (t))}^{T} P_{2} l_{i_{k}}^{2} (t) > 0 \end{matrix}

(17)

For the symmetry point in the earthy yellow domain, its position can be obtained as $2 p_{a}^{i} (t) - p_{t}^{B}$ . Thus, we have:

{\begin{matrix} {(p_{t}^{B} - p_{a}^{i} (t))}^{T} P_{1} l_{i_{k}}^{1} (t) < 0 \\ {(p_{t}^{B} - p_{a}^{i} (t))}^{T} P_{2} l_{i_{k}}^{2} (t) < 0 \end{matrix}

(18)

As seen from (17) and (18), equation (16) holds for any point in the gray and earthy yellow domain. Finally, Theorem 4 is proved. Referring to Theorem 4, the rigid constraints can be expressed as:

{(v_{r}^{i_{k}} (t + 1))}^{T} M_{t}^{i_{k}} v_{r}^{i_{k}} (t + 1) \leq 0

(19)

Because $M_{t}^{i_{k}}$ is related to $(l_{i_{k}}^{1} (t), l_{i_{k}}^{2} (t))$ , limited detection will impact the velocity planning. Taking the situation in Figure 5 as an example, the agent cannot get the full picture of the obstacle. Consequently, $(l_{i_{k}}^{1} (t), l_{i_{k}}^{2} (t))$ could not cover the whole obstacle, and the planned velocity near $(l_{i_{k}}^{1} (t), l_{i_{k}}^{2} (t))$ might lead the agent to the obstacle. To avoid this problem, we extend the gray part $O A_{1} A_{2}$ along the side filled by the obstacle, such as the green part in Figure 5. Defining $∠ A_{3} O A_{5} = φ$ , then border lines $({\tilde{l}}_{i_{k}}^{1} (t), {\tilde{l}}_{i_{k}}^{2} (t))$ related to the extended part can be obtained by:

{\begin{matrix} {\tilde{l}}_{i_{k}}^{1} (t) = T (- φ) l_{i_{k}}^{1} (t) \\ {\tilde{l}}_{i_{k}}^{2} (t) = T (φ) l_{i_{k}}^{2} (t) \end{matrix}

(20)

Figure 5.

The domain construction for roadsides avoidance.

Substituting (20) into (19), and we can get new rigid constraints.

Output constraints

Maximum velocity and angular rate should be considered for the regulator design due to dynamic constraints. The velocity will be limited by:

‖ v_{a}^{i} (t + 1) ‖ \leq v_{m}^{i}

(21)

As for the maximum angular rate restriction, a formula³⁸ confining both the velocity and the angular rate is introduced here. Then the maximum angular rate restriction can be realized by:

- {(v_{a}^{i} (t + 1))}^{T} v_{a}^{i} (t) \leq - \cos (ω_{m}^{i}) ‖ v_{a}^{i} (t) ‖ ‖ v_{a}^{i} (t + 1) ‖

(22)

Nonlinear dynamic programing model

Defining agents set causing interferences as $Z = {k_{1}, k_{2}, \dots, k_{z_{i}}}$ and the non-rounded obstacles as ${(p_{o}^{i_{s}} (t), v_{o}^{i_{s}} (t))}_{s = 1}^{n_{i}}$ with the numbers satisfying $1 \leq z_{i} \leq \min (n - 1, m_{i})$ and $\sum_{i = 1}^{n} (m_{i} - z_{i} + n_{i}) \leq m$ , the nonlinear NDP regulator can be expressed with the following equation based on the above constraints:

\begin{array}{l} J = \frac{1}{2} {(v_{a}^{t + 1} - {\bar{v}}_{a}^{t + 1})}^{T} R (v_{a}^{t + 1} - {\bar{v}}_{a}^{t + 1}) \\ s . t . \forall 1 \leq i \leq n \\ {(v_{r}^{i_{k}} (t + 1))}^{T} p_{r}^{i_{k}} (t) \leq d_{i_{k}} v_{m}^{i} \\ {(v_{r}^{i_{s}} (t + 1))}^{T} M_{t}^{i_{s}} v_{r}^{i_{s}} (t + 1) \leq 0 \\ ‖ v_{a}^{i} (t + 1) ‖ \leq v_{m}^{i} \\ {(v_{a}^{i} (t + 1))}^{T} v_{a}^{i} (t) \geq \cos (ω_{m}^{i}) ‖ v_{a}^{i} (t) ‖ ‖ v_{a}^{i} (t + 1) ‖ \end{array}

(23)

Where $d_{i_{k}} = p_{r}^{i_{k}} (t) - R_{i_{k}}$ . For any $k \in Z$ , we have $(p_{o}^{i_{k}} (t), v_{o}^{i_{k}} (t)) = (p_{a}^{i_{k}} (t), v_{a}^{i_{k}} (t))$ .

Constraints can be denoted as the compact matrices in $(24)$ to $(32)$ : $A_{t} \in R^{M \times 2 n}$ , $B_{t} \in R^{M \times 2 n^{2}}$ , $C_{t} \in R^{M}$ , $D_{t} \in R^{M}$ , $H_{t} \in R^{M \times 2 n}$ , $L_{t} \in R^{2 n^{2} \times 2 n}$ , $M_{t} \in R^{2 Mn \times 2 Mn}$ , $K_{t} \in R^{M}$ , where $M = 2 n + \sum_{i = 1}^{n} (m_{i} + n_{i})$ .

{\begin{matrix} A_{t} (\sum_{j = 1}^{i - 1} M_{j} + k, 2 i - 1 : 2 i) = - p_{r}^{i_{k}} (t) \\ A_{t} (\sum_{j = 1}^{i - 1} M_{j} + k, z_{i}^{1} : z_{i}^{2}) = p_{r}^{i_{k}} (t), k \in Z \\ A_{t} (\sum_{j = 1}^{i} M_{j}, 2 i - 1 : 2 i) = - 2 v_{a}^{i} (t) \end{matrix}

(24)

Where $M_{j} = m_{j} + n_{j} + 2$ , $z_{i}^{1} = 2 i_{k} - 1$ , $z_{i}^{2} = 2 i_{k}$ . the third formula in (24) differs from the second one, as the velocity of the obstacle is uncontrollable.

{\begin{matrix} B_{t} (\sum_{j = 1}^{i - 1} M_{j} + k, j_{i}^{1} : j_{i}^{2}) = {(d_{i_{k}})}^{2} \\ B_{t} (\sum_{1}^{i} M_{j} - 1, j_{i}^{1} : j_{i}^{2}) = 1 \\ B_{t} (\sum_{1}^{i} M_{j}, j_{i}^{1} : j_{i}^{2}) = 4 {(‖ v_{a}^{i} (t) ‖ \cos (ω_{m}^{i}))}^{2} \end{matrix}

(25)

Where $j_{i}^{1} = 2 i (n + 1) - 2 n - 1$ , $j_{i}^{2} = j_{i}^{1} + 1$ .

C_{t} (\sum_{j = 1}^{i - 1} M_{j} + k) = {(‖ v_{o}^{i_{k}} (t) ‖ d_{i_{k}})}^{2}, k \notin Z

(26)

H_{t} (\sum_{j = 1}^{i - 1} M_{j} + k, 2 i - 1 : 2 i) = - 2 v_{o}^{i_{k}} (t) {(d_{i_{k}})}^{2}, k \notin Z

(27)

D_{t} (\sum_{1}^{i} M_{j} - 1) = v_{m}^{i}

(28)

{\begin{matrix} L_{t} (i_{j}^{1} : i_{j}^{2}, 2 i - 1 : 2 i) = I^{2} \\ L_{t} (i_{j}^{1} : i_{j}^{2}, 2 j - 1 : 2 j) = I^{2}, j \neq i \end{matrix} 1 \leq i, j \leq n

(29)

Where $i_{j}^{1} = 2 n (i - 1) + 2 j - 1$ , $i_{j}^{2} = 2 n (i - 1) + 2 j$ , $I^{2}$ is the identity matrix.

Compared with other matrices, the computation of $M_{t}$ is much more complex, firstly we have:

M_{t} (M_{n}^{i - 1} : M_{n}^{i}, M_{n}^{i - 1} : M_{n}^{i}) = M_{t, i}

(30)

Where $M_{n}^{i} = 2 n \sum_{j = 1}^{i} M_{j}$ , $M_{t, i} \in ℝ^{2 n M_{i} \times 2 n M_{i}}$ , and the matrix $M_{t, i}$ is indicated as:

M_{t, i} (s_{i}^{1} : s_{i}^{2}, s_{i}^{1} : s_{i}^{2}) = S_{M}^{i} \otimes M_{t}^{i_{s}}

(31)

Where $s_{i}^{1} = 2 n (m_{i} + s - 1) + 1$ , $s_{i}^{2} = 2 n (m_{i} + s)$ . $S_{M}^{i} \in R^{n \times n}$ , and elements of $S_{M}^{i}$ equal zero except that $S_{M}^{i} (i, i) = 1$ . ⊗ indicates the Kronecker product.

$K_{t}$ is the coefficient matrix, and the element is indicated as:

{\begin{matrix} K_{t} (\sum_{j = 1}^{i - 1} M_{j} + k) = sign (d_{i_{k}}) \\ K_{t} (\sum_{1}^{i} M_{j} - 1 : \sum_{1}^{i} M_{j}) = - 1 \end{matrix}

(32)

Where $sign (*)$ is the mathematical sign function.

Referring to (24) to (32), we can rewrite (23):

\begin{array}{l} J = \frac{1}{2} {(v_{a}^{t + 1} - {\bar{v}}_{a}^{t + 1})}^{T} R (v_{a}^{t + 1} - {\bar{v}}_{a}^{t + 1}) \\ s . t . \\ {(I^{\sum M_{i}} \otimes v_{a}^{t + 1})}^{T} M_{t} (I^{\sum M_{i} \times 1} \otimes v_{a}^{t + 1}) + \\ A_{t} v_{a}^{t + 1} - D_{t} - K_{t} ◦ χ (v_{a}^{t + 1}) \leq 0 \end{array}

(33)

Where ° indicates Hadamard product. $χ (v_{a}^{t + 1})$ is a nonnegative vector, which can be computed by equation (34):

\begin{matrix} {(χ (v_{a}^{t + 1}))}^{2} = H_{t} v_{a}^{t + 1} + C_{t} \\ + B_{t} ((L_{t} v_{a}^{t + 1}) ° (L_{t} v_{a}^{t + 1})) \end{matrix}

(34)

Simulation

Three tests are conducted in this section. In test 1, agents execute missions independently, there are no external obstacles. Test 2 and test 3 verify non-rounded obstacle avoidance of the formation, agents will counter the narrow passage in test 2, and the formation must pass the road with a 90-degree turn in test 3. The nominal law ${\bar{v}}_{a}^{i} (t + 1)$ is obtained with the state error feedback controller.

\begin{matrix} {\bar{v}}_{a}^{i} (t + 1) = - K_{p} (p_{a}^{i} (t) - q_{a}^{i} (t)) \\ - K_{v} (v_{a}^{i} (t) - v_{d}^{i} (t)) + v_{a}^{i} (t) \end{matrix}

(35)

Collision avoidance

Agents causing interferences can be viewed as rounded obstacles, so in test 1 no external obstacles are designed. There are six agents executing missions in a scaled space independently, similar tests have been reported in Kiefer et al.³⁴ The initial positions and goals are shown in Table 1, and we have $ω_{m}^{i} = 0.1$ rad/s, $v_{m}^{i} = 0.1$ m/s.

Table 1.

Initial positions and goals of agents.

Initial positions (m, m)		Goals (m, m)
$p_{a}^{1} (t_{0})$	$(75, 129.9)$	$q_{a}^{1}$	$(- 73.1, - 140)$
$p_{a}^{2} (t_{0})$	$(- 75, 129.9)$	$q a^{2}$	$(78.7, - 127.7)$
$p_{a}^{3} (t_{0})$	$(- 150, 0)$	$q a^{3}$	$(149.8, 7.5)$
$p_{a}^{4} (t_{0})$	$(- 75, - 129.9)$	$q_{a}^{4}$	$(68.3, 133.5)$
$p_{a}^{5} (t_{0})$	$(75, - 129.9)$	$q_{a}^{5}$	$(- 76.1, 129.3)$
$p_{a}^{6} (t_{0})$	$(150, 0)$	$q_{a}^{6}$	$(- 149.8, - 7.6)$

Positions at steps 25, 35, and 45 are shown in Figure 6, the red crosses in subfigure (a) represent the goals, which are labeled from 1 to 6, and the blue circles indicate agents. we display the velocity of agents with blue arrows, of which ranges are scaled. The results proved that agents avoided collision successfully.

Figure 6.

Positions of agents at different time: (a) t = 10, (b) t = 25, (c) t = 35, (d) t = 40, (e) t = 45, and (f) t = 70.

Velocity and angular rate are shown in Figures 7 and 8 respectively, it can be seen that the output constraints are satisfied. Although the change of the velocity is fast sometimes, the constrained velocity makes the change limited in a reasonable scope. It seems that the accelerations might exceed the limits according to Figures 7 and 8, but the maximum change of the velocity can be controlled simultaneously, which means the accelerations limits can be fulfilled by restricting the upper and lower limit of the velocity with the proposed regulator in this paper.

Figure 7.

Velocity of agents.

Figure 8.

Angular rate of agents.

Narrow passage

The narrow passage is set as the non-rounded obstacle, the formation is expected to pass the passage. Parameters of agents are given in Table 2. Figure 9 displays the location of agents at varying steps, which showed that agents could pass the narrow passage without collisions with the proposed NDP strategy.

Table 2.

Initial positions of agents.

Positions
$p_{a}^{1} (t_{0})$	$(75, 129.9)$	$p_{a}^{4} (t_{0})$	$(- 75, - 129.9)$
$p_{a}^{2} (t_{0})$	$(- 75, 129.9)$	$p_{a}^{5} (t_{0})$	$(75, - 129.9)$
$p_{a}^{3} (t_{0})$	$(- 150, 0)$	$p_{a}^{6} (t_{0})$	$(150, 0)$

Figure 9.

Positions of agents at different time: (a) t = 1, (b) t = 20, (c) t = 35, and (d) t = 60.

Roadside

Completely autonomous motion control on road is a hot topic for agents. Assuming that agents could recognize the roadside, agents are expected to pass the turning road. Initial positions of agents are set as: $p_{a}^{1} (t_{0}) = (90, 60) m$ ; $p_{a}^{2} (t_{0}) = (80, 50) m$ ; $p_{a}^{3} (t_{0}) = (60, 50) m$ ; $p_{a}^{4} (t_{0}) = (70, 60) m$ .

Test results are displayed in Figure 10, where (a) – (d) display the positions of agents from a global perspective and (e) to (h) show the magnification of those position diagrams. Results prove that all agents could turn left safely.

Figure 10.

Positions of agents at different time: (a) t = 10, (b) t = 25, (c) t = 30, (d) t = 50, (e) t = 10 (magnification), (f) t = 25 (magnification), (g) t = 30 (magnification), and (h) t = 50 (magnification).

Conclusion

This paper focuses on obstacle and collision avoidance of systems with multiple constrained agents, and a nonlinear dynamic programing regulator is proposed for velocity control. Based on the proposed barrier function, the velocity constraints for avoiding the rounded obstacles that could be regarded as virtual circular obstacles are established, and the mathematical analysis has proved the effectiveness of the proposed velocity constraints. Considering the lack of mapping ability and limited detection while avoiding non-rounded obstacles with complex boundaries, a feasible velocity domain is created by constructing multiple half spaces based on the border lines of obstacles and convex theory, which helps release the challenge of modeling the complex obstacles. The proposed regulator is concise and easy to be realized without complex parameters compared with analytical laws, and the extensive programing space provides more feasible choices of the velocity, thus can help avoid some traps in applications. In addition, multiple kinematic constraints that are difficult to overcome via the analytical laws can be incorporated into the regulator. Through collisions and obstacles avoiding tests, the feasibility of the proposed regulator is verified, and the proposed regulator can lead agents to the destinations with only detecting information. Future work will focus on the velocity programing for obstacle and collision avoidance in three-dimensional space and more complex environments.

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) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was supported by Natural Science Foundation of Hubei Province 2018CFC865.

ORCID iD

Yasong Luo

References

Wang

Zhang

, et al. On obstacle avoidance path planning in unknown 3D environments: a fluid-based framework. ISA Trans 2021; 111(4): 249–264.

Fahimi

Nataraj

Ashrafiuon

Real-time obstacle avoidance for multiple mobile robots. Robotica 2009; 27(2): 189–198.

Zhao

Zhang

Zhao

Robust path planning for avoiding obstacles using time-environment dynamic map. Meas Control 2020; 53(1-2): 214–221.

Kala

Shukla

Tiwari

Fusion of probabilistic A* algorithm and fuzzy inference system for robotic path planning. Artif Intell Rev 2010; 33(4): 307–327.

Kapania

Gerdes

JC.

Learning at the racetrack: data-driven methods to improve racing performance over multiple laps. IEEE Trans Veh Technol 2020; 69(8): 8232–8242.

Kim

Park

Myung

Curvature path planning with high-resolution graph for unmanned surface vehicle. In: JH

Kim

Matson

Myung

, et al. (eds) Robot intelligence technology and applications 2012. Advances in intelligent systems and computing. Berlin Heidelberg: Springer, 2012, pp.147–154.

Chai

Gao

, et al. Obstacle avoidance for a hexapod robot in unknown environment. Sci China Technol Sci 2017; 60(6): 818–831.

Akka

Khaber

Mobile robot path planning using an improved ant colony optimization. Int J Adv Robot Syst 2018; 15(3): 172988141877467.

Yang

Sukkarieh

An analytical continuous-curvature path-smoothing algorithm. IEEE Trans Robot 2010; 26(3): 561–568.

10.

Walton

Meek

Ali

JM.

Planar G2 transition curves composed of cubic Bézier spiral segments. J Comput Appl Math 2003; 157(2): 453–476.

11.

Sahingoz

OK.

Generation of Bezier curve-based flyable trajectories for multi-UAV systems with parallel genetic algorithm. J Intell Robot Syst 2014; 74: 499–511.

12.

Marchidan

Bakolas

A local reactive steering law for 2D collision avoidance with curvature constraints and constant speed. Robot Auton Syst 2022; 155: 10456.

13.

Song

Hao

Path planning for unmanned surface vehicle based on predictive artificial potential field. Int J Adv Robot Syst 2020; 17(2): 172988142091846.

14.

Savvas

. Closed form navigation functions based on harmonic potentials. In: Proceedings of the 2011 50th IEEE conference on decision and control and European control conference (CDC-ECC), Orlando, FL, 12–15 December 2011. New York: IEEE.

15.

Masoud

. A harmonic potential, space-time navigation control with obstacle forecast, avoidance and guaranteed time of arrival. In: Proceedings of the 2021 American control conference (ACC), New Orleans, LA, 25–28 May 2021. New York: IEEE.

16.

Kim

Khosla

PK.

Real-time obstacle avoidance using harmonic potential functions. In: Proceedings of the 1991 IEEE international conference on robotics and automation, Sacramento, CA, 09–11 April 1991. New York: IEEE.

17.

Vlantis

Vrohidis

Bechlioulis

CP.

Robot navigation in complex workspaces using harmonic maps. In: Proceedings of the 2018 IEEE international conference on robotics and automation (ICRA), Brisbane, QLD, 21–25 May 2018. New York: IEEE.

18.

Verginis

Dimarogonas

DV.

Adaptive robot navigation with collision avoidance subject to 2nd-order uncertain dynamics. Automatica 2021; 123: 109303.

19.

Koditschek

Rimon

Robot navigation functions on manifolds with boundary. Adv Appl Math 1990; 11(4): 412–442.

20.

Rimon

Koditschek

DE.

Exact robot navigation using artificial potential functions. IEEE Trans Robot Autom 1992; 8(5): 501–518.

21.

Lafmejani

Farivarnejad

Berman

Adaptation of gradient-based navigation control for holonomic robots to nonholonomic robots. IEEE Robot Autom Lett 2021; 6(1): 191–198.

22.

Loizou

SG.

The navigation transformation. IEEE Trans Robot 2017; 33(6): 1516–1523.

23.

Hacohen

Shoval

Shvalb

Probability navigation function for stochastic static environments. Int J Control Autom 2019; 17(8): 2097–2113.

24.

Yao

Obstacle-avoiding path planning for multiple autonomous underwater vehicles with simultaneous arrival. Sci China Technol Sci 2019; 62(1): 121–132.

25.

Yao

Wang

UAV feasible path planning based on disturbed fluid and trajectory propagation. Chin J Aeronaut 2015; 28(4): 1163–1177.

26.

Yao

Zhao

Zhu

Path planning for autonomous underwater vehicles with simultaneous arrival in ocean environment. IEEE Syst J 2020; 14(3): 3185–3193.

27.

Yao

Wang

Cooperative path planning with applications to target tracking and obstacle avoidance for multi-UAVs. Aerosp Sci Technol 2016; 54: 10–22.

28.

Savkin

Wang

A simple biologically inspired algorithm for collision-free navigation of a unicycle-like robot in dynamic environments with moving obstacles. Robotica 2013; 31(6): 993–1001.

29.

Yuan

Zhang

, et al. A novel real-time collision risk awareness method based on velocity obstacle considering uncertainties in ship dynamics. Ocean Eng 2021; 220: 108436.

30.

Song

Chen

Dong

, et al. Collision avoidance planning for unmanned surface vehicle based on eccentric expansion. Int J Adv Robot Syst 2019; 16(3): 172988141985194.

31.

Sun

Ran

Zhang

, et al. AUV 3D path planning based on the improved hierarchical deep Q network. J Mar Sci Eng 2020; 8(2): 145.

32.

Silva Junior

AGD

Santos

DHD

Negreiros

APF

, et al. High-level path planning for an autonomous sailboat robot using Q-learning. Sensors 2020; 20: 1550.

33.

Wang

Ames

Egerstedt

Safety barrier certificates for collisions-free multirobot systems. IEEE Trans Robot 2017; 33(3): 661–674.

34.

Kiefer

Graichen

Kugi

Trajectory tracking of a 3DOF laboratory helicopter under input and state constraints. IEEE Trans Control Syst Technol 2010; 18(4): 944–952.

35.

Wang

Duan

Wang

, et al. LQ synchronization of discrete-time multiagent systems: a distributed optimization approach. IEEE Trans Autom Control 2019; 64(12): 5183–5190.

36.

Wang

Duan

, et al. Linear quadratic optimal consensus of discrete-time multi-agent systems with optimal steady state: A distributed model predictive control approach. Automatica 2021; 127: 109505.

37.

Boyd

Vandenberghe

Faybusovich

Convex optimization. IEEE Trans Autom Control 2006; 51(11): 1859–1859.

38.

Sun

Dai

Liu

, et al. Robust MPC for tracking constrained unicycle robots with additive disturbances. Automatica 2018; 90: 172–184.

Collision and obstacle avoidance strategy for multi-agent systems with velocity dynamic programing

Abstract

Keywords

Introduction

Obstacle avoidance

Constraints of the regulator

Rounded obstacles

Non-rounded obstacles

Rigid constraints

Output constraints

Nonlinear dynamic programing model

Simulation

Collision avoidance

Narrow passage

Roadside

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References