A fully distributed motion coordination strategy for multi-robot systems with local information

One challenge for multi-robot systems (MRSs) is the design of coordination strategies between robots that enable them to perform operations safely and efficiently in a shared workspace while achieving individual/group motion objectives [1]. This problem was originated from 1980s and has been extensively investigated since. In recent years, the attention that has been put on this problem has grown significantly due to the emergence of new applications, such as smart transportation and service robotics. The existing literature can be divided into two categories: path coordination and motion coordination. The former category plans and coordinates the entire paths of all the robots in advance, while the latter category focuses on decentralized approaches that allow robots to resolve conflicts online as the situation occurs¹¹1In some literatures, these two terms are also used interchangeably. In this paper, we try to distinguish between the two as explained above. [2]. This paper aims at developing a fully distributed strategy for multi-robot motion coordination (MRMC).

Depending on how the controller is synthesized for each robot, the literature concerning MRMC can further be classified into two types: the reactive approach and the planner-based approach. Typical methods that generate reactive controllers consist of potential-field approach [3], sliding mode control [4] and control barrier functions [5]. These reactive-style methods are fast and operate well in real-time. However, it is well-known that these methods are sensitive to deadlocks that are caused by local minima. Moreover, guidance for setting control parameters is not analyzed formally when explicit constraints on the system states and/or inputs are presented [2]. Apart from the above, other reactive methods include the generalized roundabout policy [6] and a family of biologically inspired methods [7].

An early example of the planner-based method is the work of Azarm and Schmidt [8], where a framework for online coordination of multiple mobile robots was proposed. Based on this framework, various applications and different motion planning algorithms are investigated. Roughly speaking, the motion planning algorithms used in planner-based approaches can be divided into two types: fixed-path planning [9, 10] and trajectory planning [8, 11, 12], while the former one differs from the latter one in that the motions for individual robots are fixed along specific paths. Guo and Parker [11] proposed a MRMC strategy based on the D^∗ algorithm [12]. In this work, each robot has an independent goal position to reach and know all path information. In [13], a distributed bidding algorithm was designed to coordinate the movement of multiple robots, which focuses on area exploration. In the work of Liu [10], conflict resolution at intersections was considered for connected autonomous vehicles, where each vehicle is required to move along a pre-planned path. In general, the fixed-path planning method is more efficient. Its major disadvantage, however, lies in the fact that it fails more often. A literature review on MRMC can be found in [1].

In this paper, we investigate the MRMC problem on a realistic setup. Robots are assumed to have limited sensing capabilities and both velocity and input constraints are considered. Conflicts are assumed to be local and can occur at arbitrary locations in the workspace. To cope with this setup, a fully distributed MRMC strategy is proposed. The contributions of this paper can be summarized as follows. Building on top of a cell decomposition, a formal definition of spatial-temporal conflict is introduced first. This definition characterizes when replanning is required for each robot. Then, a simple rule is proposed for online planning order assignment, which is deadlock-free when only local information is available to each robot. Finally, a two-step motion planning process is proposed, i.e., the fixed-path planning is activated first while the trajectory planning is activated if and only if the fixed-path planning returns no feasible solution, which allows us to leverage both the benefits of fixed-path planning and trajectory planning.

The remainder of the paper is organized as follows. In Section II, notation and preliminaries on graph theory are introduced. Section III formalizes the considered problem. Section IV presents the proposed solution in detail, which is verified by simulations in Section V. Conclusions are given in Section VI.

Consider a group of $N$ mobile robots, whose dynamics are given by:

where $p_{i}:=(x_{i},y_{i})$ is the Cartesian position, $\theta_{i}$ is the orientation, $v_{i},\omega_{i}$ are respectively the tangential velocity and the angular velocity, $F_{i}$ is the force input, and $\tau_{i}$ is the torque input of robot $i$. For convenience, we define $\xi_{i}:=(x_{i},y_{i},\theta_{i},v_{i},\omega_{i})$ and $u_{i}:=(F_{i},\tau_{i})$. Then, (1) can be written as $\dot{\xi_{i}}=f(\xi_{i},u_{i})$, where $f(\xi_{i},u_{i})=(v_{i}\cos(\theta_{i}),v_{i}\sin(\theta_{i}),\omega_{i},0,0)+(0,0,0,u_{i})$. The velocity and input of each robot $i$ are subject to the constraints

Let $\mathbb{V}_{i}:=\{v_{i}:|v_{i}|\leq v_{i}^{\max}\},\mathbb{W}_{i}:=\{\omega_{i}:|\omega_{i}|\leq\omega_{i}^{\max}\}$ and $\mathbb{U}_{i}:=\{(F_{i},\tau_{i}):|F_{i}|\leq F_{i}^{\max},|\tau_{i}|\leq\tau_{i}^{\max}\}$.

Given a vector $\xi_{i}$, define the projection operator $\verb"proj"_{p_{i}}(\xi_{i}):\mathbb{R}^{5}\to\mathbb{R}^{2}$ as a mapping from $\xi_{i}$ to its first 2 components $p_{i}$. A curve ${\bm{\xi}}_{i}:[0,T[\to\mathbb{R}^{5}$ is said to be a trajectory of robot $i$ if there exists input $u_{i}(t)\in\mathbb{U}_{i}$ satisfying $\dot{\bm{\xi}}_{i}(t)=f({\bm{\xi}}_{i}(t),u_{i}(t))$ for all $t\in[0,T[$. A curve $\textbf{p}_{i}:[0,T[\to\mathbb{R}^{2}$ is a position trajectory of robot $i$ if $\textbf{p}_{i}(t)=\verb"proj"_{p_{i}}({\bm{\xi}}_{i}(t)),\forall t\in[0,T[$. Given a time interval $[t_{1},t_{2}],t_{1}<t_{2}$, the corresponding position trajectory is denoted by $\textbf{p}_{i}([t_{1},t_{2}])$.

Supposing that the sensing radius of each robot is the same, given by $R>0$, then the communication graph formed by the group of robots is undirected. The neighboring set of robot $i$ at time $t$ is given by $\mathcal{N}_{i}(t)=\{j:\|x_{i}(t)-x_{j}(t)\|\leq R,j\in\mathcal{V},j\neq i\}$, so that $j\in\mathcal{N}_{i}(t)\Leftrightarrow i\in\mathcal{N}_{j}(t),i\neq j,\forall t$. The group of robots are working in a common workspace $\mathbb{X}\subset\mathbb{R}^{2}$, which is populated with $m$ closed sets $O_{i}$, corresponding to obstacles. Let $\mathbb{O}={\cup}_{i}O_{i}$, then the free space $\mathbb{F}$ is defined as $\mathbb{F}:=\mathbb{X}\setminus\mathbb{O}$.

Each robot $i$ is subject to its own task specification $\varphi_{i}$ (in this work, we consider $\varphi_{i}$ to be a reach-avoid type of task expressed as a linear temporal logic (Chapter 5 [15]) formula). Given a position trajectory $\textbf{p}_{i}$, the satisfaction relation is denoted by $\textbf{p}_{i}\models\varphi_{i}$. Given the position $p_{i}$ of robot $i$, we refer to its footprint $\phi(p_{i})$ as the set of points in $\mathbb{X}$ that are occupied by robot $i$ in this position. The objective of the system is to ensure that the task specification $\varphi_{i}$ of each robot is satisfied efficiently (in the sense that a pre-defined objective function, e.g., $J_{i}$, is minimized), while safety (no inter-robot collision) of the system is guaranteed.

Note that in this paper, it is assumed that each robot is not aware of the existence of other robots. Moreover, each robot has only local view and local information. Under these settings, the MRMC problem has to be broken into local distributed motion coordination problems and solved online for individual robots. Let $\textbf{p}_{j}([t,t_{j}^{*}(t)]),j\in\mathcal{N}_{i}(t)$ be the local position trajectory of robot $j$ that is available to robot $i$ at time $t$, where $t_{j}^{*}(t)$ is determined by $t$. Then, the (online) motion coordination problem for robot $i$ is formulated as

where constraint (3c) means that two robots can not arrive at the same cell at the same time for all $t^{\prime}\in[t,t_{j}^{*}(t)]$, thus guarantees no inter-robot collision occurs.

The proposed solution to the motion coordination problem (3) consists of two layers: 1) an initialization layer and 2) an online coordination layer.

We illustrate the results of the paper on a MRS consisting of $N=7$ robots. The velocity and input constraints for each robot are given by $|v_{i}|\leq 2m/s,|\omega_{i}|\leq 115rad/s,|F_{i}|\leq 2m/s^{2},|\tau_{i}|\leq 115rad/s^{2}$ and the sensing radius is $R=5m$. The common workspace for the group of robots is depicted in Fig. 2 ($xy$ axis), where the gray areas represent the obstacles and a grid representation with grid size $0.5m$ is implemented as cell decomposition. For each robot, the task specification is given by $\varphi_{i}:=\square\neg\mathbb{O}\wedge\lozenge\square X_{i}^{f},\forall i$, where $X_{i}^{f}$ (marked as colored region in Fig. 2) represents the target set for robot $i$, while $\neg$, $\square$ and $\lozenge$ are respectively “negation”, “always” and “eventually” operators in a linear temporal logic formula.

The initial optimal trajectories for each robot are depicted in Fig. 2, where the colored arrows show the moving direction of each robot. It can be seen that conflicts (i.e., inter-robot collisions) occur between robot pairs $(1,3),(1,7),(4,5)$ and $(3,6)$. During online implementation, conflicts are detected by each robot and replanning is conducted by robots 1, 4 and 6 at time instants $19.7s,7.5s$ and $8.4s$, respectively. In the motion planning module, the ICLOCS2 [23] toolbox is implemented to solve the FPPP (8) and the TPP (9). The real-time moving trajectory for each robot is shown in Fig. 3, where all the conflicts are resolved.

The real-time evolution of velocities $(v_{i},\omega_{i})$ and inputs $(F_{i},\tau_{i})$ for each robot are given in Fig. 4 and Fig. 5, respectively. One can see that the tangential and angular velocity constraints and the force and torque input constraints are satisfied by all robots at all times. All the simulations were run in Matlab 2018b on a DELL laptop of 2.6GHz using Intel Core i7.

In this paper, the online MRMC problem is considered. Under the assumptions that each robot has only local view and local information, and subject to both velocity and input constraints, a fully distributed motion coordination strategy was proposed for steering individual robots in a common workspace, where each robot is assigned independent task specifications. It was shown that the proposed strategy can guarantee collision-free motion of each robot. A next step is to perform real-world experiments.

The authors would like to thank Yulong Gao for valuable discussions.