Control synthesis for multiple mobile robot systems

Abstract

This work continues our study on the control synthesis for multiple mobile robot systems (MMRS). We assume a hybrid approach that comprises the supervisory control level, based on a discrete event model of MMRS, and the robot control level, based on a continuous time model of the robot motion. Our objective is to further develop the control concept towards its implementation in a real-world application – a testbed for a fleet of six laboratory robots. In the first part of the paper, we develop a methodology of the supervisory control synthesis, that employs the Petri net formalism and formally ensures the required logics of MMRS operation, as well as propose a relevant architecture of the supervisor. The second part is focused on the low-level robot control and control procedures enabling modification of the robot motion according to the supervisor’s decisions. A simulation case is presented that illustrates the operation of the system.

Keywords

multiple mobile robot system hybrid control discrete event system continuous time system

Introduction

The use of a mobile robot team in place of one robot substantially increases the performance of many robotic applications, including those related to area searching, search and rescue, interplanetary exploration, extraction of minerals, agriculture, forestry, or transport. A key issue in the design of such systems is to coordinate the movement of a number of robots operating in the same workspace. Regardless of their tasks, the robots must be able to effectively share a common area in order to prevent the mutual disruption of traffic and effectively pursue their missions.

Representative results for this type of research can be found, among others, in the following papers. Tomlin et al. (1998) and Lygeros et al. (1998) contribute with hybrid control solutions for aircraft and highway systems, respectively. Pecora et al. (2012) and La Valle and Hutchinson (1998) focus on conflict resolution and optimal motion planning for multiple mobile robots. Inalhan et al. (2002) present a decentralized optimization method for solving the coordination problem of interconnected systems with multiple decision makers. Andreasson et al. (2015) adopt constraints on trajectories in time and space that are imposed dynamically on the system. Some works, such as Basilico et al. (2009), apply a Leader–Follower strategy for planning mobile robot patrolling. Useful application of prioritized control can be found in Cap et al. (2015). Decentralized algorithms for collision avoidance are proposed in Ferrera et al. (2013) and Pallottino et al. (2007). Difficulty of the system control that increases with density of robots in shared workspace is studied in Ferrera et al. (2017).

The main contribution of these works are methodologies of collision-free control of robot movement. The resulting algorithms have, however, two major drawbacks: (a) because of their high computational complexity, they are not scalable, and (b) they do not guarantee the correct operation of the system in terms of ensuring the completion of the robot missions. The ineffectiveness of these models in providing the above properties is mainly due to the assumed representation of the robot system, whose operation is abstracted in continuous time. Devoid of these disadvantages is the approach introduced in Roszkowska (2005), Reveliotis and Roszkowska (2011) and Roszkowska and Reveliotis (2013), where the logic of robot coordination is developed using the Discrete Event System (DES) formalism. The proposed model ensures correct space sharing by a group of robots through imposing certain constraints on their motion, and can be applied to mobile robots accomplishing any arbitrarily assumed missions, and for both centralized and distributed supervisory control architecture. To respect the requirements of a so-defined DES-based supervisory control scheme, the robots need to modify their individual motion control, based on the Continuous Time System (CTS) abstraction. Consequently, the control of a team of multiple mobile robots requires a hybrid control system, incorporating both DES and CTS control layers.

Such an approach was previously considered in the papers by Roszkowska et al. (2018, 2019) and is further developed in this work. More specifically, all these three papers deal with the hybrid control synthesis for multiple mobile robot systems (MMRS), but focus on its different aspects. In Roszkowska et al. (2018), we proposed the logic that formally ensures collision- and deadlock-free robot coordination in MMRS, implemented it in the form of a composite-automaton supervisor, and combined with time models of robot motion processes in the Matlab/Simulink/Stateflow environment. The obtained MMRS model ensures correct co-operation of the robots and can be directly used for the prediction or simulation-based optimization of the system performance. The main result of Roszkowska et al. (2019) is a comprehensive methodology of the control synthesis for MMRS. We proposed a hybrid system that consisted of four control levels: concurrency control (DES based), mode control (DES based), priority control(DES/CTS based), and motion control (CTS based), and demonstrated its operation through an application developed in The Stage Robot Simulator environment.

This work is an extended and more mature version of the paper Roszkowska and Jakubiak (2020) originally accepted by CoDIT20, and further develops the control concept towards its implementation in a real-world application – a testbed for a fleet of six laboratory robots. The next section sets the research framework, specifying the principles and requirements of the MMRS operation, and recapturing the general concept of the hybrid control for MMRS proposed in the earlier works. Capitalizing on these results, we then introduce a methodology of the supervisory control synthesis that employs the Petri net formalism and ensures the required logics of MMRS operation. The architecture of the supervisor using such models is proposed in the following section. The next two sections focus on the low-level robot control and control procedures enabling modification of the robot motion according to the supervisor’s decisions. The final section concludes the presented research.

Hybrid control for MMRS

We consider a MMRS viewed as a group of autonomous mobile robots sharing a 2D space. Each robot performs a mission that requires it to travel along a specific path. The path of each robot is planned independently, without taking into account any positional constraints introduced by the paths of other robots. The robots operate asynchronously and are able to control their motion with path-following algorithms that allow each of them to correctly perform its mission when alone on the stage. When sharing the motion space, the robots must refine their motion strategies in order to avoid collisions, through modification of their paths, velocity profiles or both.

The objective of the MMRS control is to ensure that the operation of the system is correct and efficient, which generates the following problems:

1. How to modify dynamically the initially assumed motion control of the robots so that:

at each moment of their motion, the areas occupied by the robots are disjoint,

in a finite time interval, all the robots will have accomplished their missions.

2. How to induce, within the admissible (i.e. observing requirements (1.a) and (1.b)) robot concurrent operation, efficient MMRS behaviour.

As can be noticed, satisfaction of requirement (1.a) implies collision-free motion of the robots, whereas requirement (1.b) ensures that the modification of the initially assumed robot motion strategies will guarantee their convergence to the destination points and occurrence of no such side effects as deadlocks or starvation. Requirement (2) implies the need of a flexible model of MMRS control that leaves room for the optimization of the system efficiency, and of tools to carry it out. To achieve realization of these postulates, we propose a hybrid control system that consists of two control levels:

supervisory control

robot control

Figure 1 presents a general scheme of such a control system, comprising a central supervisor and local robot controllers.

Figure 1.

General scheme of the system.

Both the supervisory control and the upper-level robot control models are discrete event abstraction, whereas the low-level robot control is based on a continuous time model. In the following sections we discuss this concept in more detail.

Supervisory control model

As mentioned in the previous section, the supervisor employs a DES model of an MMRS that represents the concurrent movement of the robots along their specific paths. To develop such models it is convenient to use the formalism of a class of Petri nets (Reisig 1985), defined as follows.

Definition 1. A place/transition system (P/T system) is a triple $N = (P, T, F, M_{0})$ such that:

• $(P \cup T, F)$ is a net, where

- $P \cup T$ , $P \cap T = Ø$ , is the node set, that comprises two types of nodes: places $p \in P$ and transitions $t \in T$ . The set $T$ is further partitioned into two sets $T_{C} \cup T_{O}$ , $T_{C} \cap T_{O} = Ø$ , of controllable and observable (non-controllable) transitions.

- $F \subseteq (P \times T) \cup (T \times P)$ is the flow relation, that constitutes the arc set of the net.

• $M_{0} : P \to N$ is the initial state of the system, called the initial marking.

Definition 2. The state of a P/T system is represented by marking $M : P \to N$ , that is initially given by $M_{0}$ and then changes as a result of firing transitions according to the following rules:

• only an enabled transition $t$ can fire

• a transition $t$ is enabled in marking $M$ if and only if $\forall p \in^{•} t : M (p) \geq 1$

• if transition $t$ fires in marking $M$ then it causes the change of the marking to $M'$ such that:

M' (p) = {\begin{matrix} M (p) - 1 if p \in^{•} t \ t^{•} \\ M (p) + 1 if p \in t^{•} \^{•} t \\ M (p) otherwise \end{matrix}

where:

${}^{•}t = {p : (p, t) \in F}$ is the set of input places of $t$ ,

$t^{•} = {p : (t, p) \in F}$ is the set of output places of $t$ .

It is assumed that each robot $A_{i}$ , $i \in 1, \dots, n$ is represented by a disk of a given radius $ρ_{i}$ , and is supposed to follow some specific path $p_{i}$ . The discrete character of the MMRS model arises from that the robot paths are arbitrarily partitioned into sectors. A robot is allowed to move autonomously within a sector, yet it can only transit to the next sector if commanded to do it by the supervisor. Then, the motion process of a robot is viewed as a sequence of states corresponding alternately to the travel along the respective path sectors and to the transition from one sector to the next one.

Figure 2 presents a P/T model of the process of robot $A_{i}$ motion along path $p_{i}$ partitioned into $n_{i}$ sectors. The depicted places and transitions have the following meaning.

Places $p_{i 0}$ and $p_{i, (n_{i} + 1)}$ represent the state of robot $A_{i}$ before the start and after the end of its travel, respectively. Places $q_{i 1}$ and $q_{i, (n_{i} + 1)}$ represent the entrance of robot $A_{i}$ onto its path and the exit of $A_{i}$ from its path, respectively.

Place $p_{ij}$ , $j = 1, \dots, n_{i}$ , represents the travel of robot $A_{i}$ along sector $p_{ij}$ , and place $q_{i, j}$ , $j = 2, \dots, n_{i}$ , represents the transit of robot $A_{i}$ from sector $p_{i - 1}$ to sector $p_{i}$ .

Transitions $t_{ij}$ , $i = 1, \dots, n_{i}$ , and $t_{i, (n_{i} + 1)}$ are controllable events and represent the permissions for robot $A_{i}$ to enter sector $p_{ij}$ and leave the path, respectively.

Transitions $u_{i 1}$ and $u_{i, n_{i} + 1}$ are observable events that occur when the disk of robot $A_{i}$ entirely enters and leaves the path, respectively. Transition $u_{ij}$ , $j = 2, \dots, n_{i}$ is an observable event that occurs when the disk of robot $A_{i}$ entirely enters sector $p_{ij}$ , that is, no more overlaps sector $p_{i, (j - 1)}$ .

Figure 2.

P/T system representing the motion of robot $A_{i}$ along its path $p_{i}$ partitioned into $n_{i}$ sectors.

To avoid collisions among the robots, we will constrain their concurrent movement based on the conflict relation among the path sectors.

Definition 3. For a set of $n$ robot paths, respectively partitioned into $n_{i}$ , $i = 1, \dots, n$ , sectors, two sectors are in conflict if they belong to two distinct paths and the minimal distance between these sectors is shorter than the diameter of the robot disk.

Then the collision-avoidance policy consists of using only one sector at a time, for each pair of conflict sectors. That is, for each pair of path sectors $p_{ij}$ and $p_{kl}$ that are in conflict, robot $A_{i}$ must not be allowed to transit to sector $p_{ij}$ if robot $A_{k}$ is currently travelling in path sector $p_{kl}$ . To implement this policy in the P/T model of $n$ mobile robots, for each pair of conflict sectors $(p_{ij}, p_{kl})$ , we introduce an additional place ${{}_{ij}r}_{kl}$ that prevents robots $A_{i}$ and $A_{k}$ from using these sectors concurrently.

The assumed concept of MMRS modelling is illustrated through an example. Figure 3 depicts the paths of three robots, and their partition into sectors. As can be noticed, the following pairs of sectors are in conflict (as the minimal distance between the sectors of each pair is less than the diameter of the robots): $(p_{12}, p_{23})$ , $(p_{22}, p_{34})$ , $(p_{23}, p_{33})$ , and $(p_{24}, p_{32})$ . Next, Figure 4 shows the Petri net (PN) model of the robot motion processes that comprises the sub-systems created in the way illustrated in Figure 2 for each robot path of Figure 3, and the additional places $r \in {_{12} r_{23},_{22} r_{34},_{23} r_{33},_{24} r_{32}}$ , corresponding to the pairs of sectors that are in conflict. As can be noticed, for each such a pair $(p_{ij}, p_{kl})$ , there is a guard – place ${{}_{ij}r}_{kl}$ that loses its token when either robot $A_{i}$ gets the permission to enter its j-th sector or robot $A_{k}$ gets the permission to enter its l-th sector. The token only returns to the place when robot $A_{i}$ or robot $A_{k}$ leaves its respective sector. As this token is necessary to enable the transitions representing the permission, the P/T model prevents concurrent occupation of the conflict sectors, and thus occurrence of collisions among the robots.

Figure 3.

Example paths of three robots with their partition into sectors.

Figure 4.

Petri net model of the concurrent, collision-free movement of the robots depicted in Figure 3.

Remark: It is not hard to notice that the marking of the conflict-relation places $r$ depends on the marking of the (robot motion) process places $q$ and $p$ . Moreover, for each robot $A_{i}$ , only one place in its process sub-net is marked in any marking of the system. Thus, the marking of the net can be uniquely identified by the set of the marked places ${x_{1 j_{1}}, x_{2 j_{2}}, \dots, x_{n j_{n}}}$ , where $x_{ij} \in {p_{ij}, q_{ij}} \subset P \cup Q$ . For example, the marking depicted in Figure 4 is ${p_{11}, p_{23}, p_{31}}$ .

As demonstrated above, the proposed collision-avoidance policy and its implementation in the P/T system solve problem 1(a) defined in section Hybrid control for MMRS. To satisfy requirement 1(b), it is necessary to further constrain the dynamics of MMRS in order to avoid all the states from which the final state of the system (when all the robots have completed their travel) is not reachable. To do that, we need to forbid each change of the marking $M \to^{t} M'$ caused by firing a transition such that $M'$ is a deadlock or unavoidably leads to a deadlock. To illustrate this concept consider the following example.

In the system presented in Figure 4, firing transition $t_{24}$ in the current marking $M = {p_{11}, p_{23}, p_{31}}$ brings the system to marking $M' = {p_{11}, q_{24}, p_{31}}$ that is correct, as there exists a transition sequence $σ = u_{24} t_{25} u_{25} t_{26} u_{26} t_{12} u_{12} t_{13} u_{13} t_{14} u_{14} t_{32} u_{32} t_{33} u_{33} t_{34} u_{34} t_{35} u_{35} t_{36} u_{36}$ such that $M' \to^{σ} M_{fin}$ , that brings the system from $M'$ to the final marking $M_{fin} = {p_{14}, p_{26}, p_{36}}$ . However, firing of transition $t_{32}$ results in $M ″ = {p_{11}, p_{23}, q_{32}}$ that is a pre-deadlock marking as, after firing the only enabled transition $u_{32}$ , the system reaches the marking $M ″' = {p_{11}, p_{23}, p_{32}}$ when no transition is enabled, i.e. a deadlock.

To ensure the correct operation of MMRS in terms of the requirement 1(b), it is necessary to restrict the concurrent motion of the robots so that no deadlocks can occur in the system. In the literature, two general approaches to deadlock handling are considered: deadlock prevention, that requires off-line analysis of the model of concrete processes before its application in the controller, and deadlock avoidance, that consists in the development of an algorithm applicable for the models of any group of processes within the considered class. These algorithms are used online, and their role is to distinguish between safe and not-safe (leading directly or indirectly to deadlocks) state changes. Both of the discussed approaches are system specific, and to our best knowledge, except for our earlier results, no deadlock-handling methods have been proposed for the coordination of free-range robots, as those considered here. Moreover, in view of the required flexibility of MMRS, allowing dynamic changes of the robot motion processes (assignment of new missions, path modifications), solutions based on off-line analysis of the changing models are hardly acceptable. Therefore we focus on the development of a deadlock-avoidance policy (DAP) for MMRS. The DAP defined below is a modified concept of such a policy presented in Roszkowska (2005).

Definition 4. In the considered P/T model of MMRS, marking $M$ is ordered if there exists a permutation $z_{1}, z_{2}, \dots, z_{n}$ of the set $N = {1, 2, \dots, n}$ such that for each pair $(z_{i}, z_{k}) \in N$ the following is true. If $z_{i} > z_{k}$ then $p_{z_{k}, j}, q_{z_{k}, l} \notin M$ , where $p_{z_{k}, l}$ is any sector of robot $A_{z_{k}}$ that is in conflict with any sector $p_{z_{i}, j}$ of robot $A_{z_{i}}$ that lies between its currently occupied sector (defined by M) and the nearest non-conflict sector.

The ordered markings have the following property.

Theorem 1. In the considered P/T model of MMRS, for each ordered marking $M$ , there exists a sequence of transitions $σ$ that brings the system to the final marking, $M \to^{σ} M_{fin}$ .

Outline of proof: Definition 4 implies that starting from marking $M$ , all the robots, one by one, in the order $A_{z_{1}}$ , $A_{z_{2}}$ , …, $A_{z_{n}}$ can reach a non-conflict sector, that corresponds to marking $M'$ . Next, again one by one, in any order, the robots can reach their respective final states.

Then the DAP is constructed as follows. For each transition $t$ enabled in any marking $M$ , firing of $t$ is safe if marking $M'$ resulting from $M \to^{t} M'$ is ordered.

As demonstrated, the constructed DAP satisfies requirement 1(b). The solution of the efficiency problem depends on the optimization criteria used and generally requires a simulation-based solution. A simulation system can employ the same supervisor architecture as that to be used for the control of real MMRS, discussed in the next section.

Architecture of the supervisor

As mentioned before, at the supervisory control level, MMRS is viewed as a DES that represents in a discrete way the concurrent movement of the robots along their specific paths. The event set of the system is the union of the sets of events associated with each particular robot. There are two types of events: controllable events, that represent decisions of the supervisor sent to the real robot system (or the plant), and observable events, that occur in the plant and are reported to the supervisor.

The supervisory control consists in inducing through controllable events a trajectory in the state space that is admissible with respect to the requirements (1) and advantageous from the viewpoint of requirement (2). The latter defines some efficiency criterion as, for example, the time required for the completion of the missions of all the robots, which should be possibly short. The decisions corresponding to such events are calculated jointly by three modules: System Manager (SM), Deadlock Avoidance Policy (DAP), and Real-Time Scheduler (RTS), as depicted in Figure 5.

Figure 5.

Architecture of the supervisor.

The role of System Manager is to keep the DES model up to date, which requires: (i) recalculation of the parameters of the P/T model of MMRS in the case of a new task assignment to some robot or when replanning its path, and (ii) calculation of the new state of the model at each event occurrence. Next to this update, SM can be called by DAP or RTS module, that in order to evaluate a potential decision may need to predict the changes it yields.

A controllable event is selected among the transitions that are enabled in the current marking $M$ of the P/T model, and are positively verified by the DAP module. If there are more such transitions, the RTS module decides about the priority of their firing. Firing of a transition $t_{ij}$ is followed by issuing the permission to robot $A_{i}$ to transit to its next path sector $p_{ij}$ and changing the current marking of the P/T model according to $M' \to^{t_{ij}} M'$ .

To conform to the decisions of the supervisor, the local controllers need to be able to enforce the required behaviour of the robots. A robot must inform the supervisor about certain events occurring during its travel, and be prevented from the transition to the next sector until it is granted the permission. Thus, the robot may have to slow down and even come to a stop, wait until the permission is received, and resume its travel. Such an operation can be obtained by establishing a number of control modes, and providing each robot with an additional control level, a DES-based supervisor responsible for the appropriate selection of the control procedures.

Robot controller

The continuous time system (CTS) contains the modules responsible for low-level control of robots’ navigation. Each robot supplies CTS with two components (cf. Figure 1): (i) robot controller that is an interface between the supervisor of the DES layer and the robot itself, and (ii) low-level real-time navigation procedures of the robot. Each robot operates independently from the others, communicating with the supervisor via the interface of the robot controller only. It is assumed that the robots are homogeneous at the functional and interface level, so their controllers described below are identical.

The operation of the robot controller can be divided into two phases: initialization, when the robot receives the path and gets ready to begin the mission, and the mission execution.

It is assumed that during the initialization phase, each robot occupies its private area, for example, in the docking station, and no conflict with other robots can occur. Therefore no supervision is required at this stage of the robot operation. The mission execution phase begins when the robot controller is properly initialized, that is, it has obtained the specification of a correct path partitioned into sectors, and the mobile robot has moved to the location at the beginning of the path, which is the initial point of the first sector. Then the mobile robot waits for a permission to enter the first sector and begin the mission.

During the mission the robot moves along the path divided into segments. In each path segment the robot controller determines five characteristic points:

s_s– segment start, where geometric segment begins,

ep– entry point, where the whole robot is within the current segment and the outline of the robot does not overlap with the previous segment which can be therefore released,

dp– decision point, until which the robot must receive a permission to enter the next segment without decreasing velocity,

sp– stop point, where the robot outline is still in a whole within the current segment, before entering to the next segment,

s_e– segment end, where the geometric segment ends.

It must be noted that between $s_{s}$ and $ep$ as well as between $sp$ and $s_{e}$ in addition to the current segment, the robot also occupies (i.e. overlaps) one of the adjacent segments.

The robot controller manages the movement of the robot according to the state machine with five states related to the current velocity of the robot and the location of the robot with respect to the characteristic points of the segment. The diagram of the state machine with a single path segment is presented in Figure 6.

Figure 6.

Single robot motion states in a sector.

The states indicated in the figure are:

v₀– the robot is stopped before entering the next segment, waiting for a permission,

v₊– acceleration – robot is allowed to continue its motion, increasing the velocity until it reaches its cruising speed,

v_m– regular motion – the robot moves with the cruising speed along the path segment, expecting a permission to enter the next segment; if the permission is not received until the decision point ( $dp$ ) the robot switches to deceleration,

$v_{m}^{a}$ – regular motion with a permission to enter the next segment – the robot continues movement with a cruising speed to the next segment,

v– deceleration – after reaching the decision point without a permission to enter the next segment the robot begins to slow down to stop before passing the stop point of the segment; if a permission is obtained during deceleration the robot immediately switches to acceleration without a full stop.

The states of the robot controller represent interface between any single robot and the supervisor. The coordination is achieved with communication messages. In the messages coming from the supervisor, the controller receives permissions to enter the next path sector. In return, the controller sends three types of messages:

entering the next sector,

releasing the previous sector and

confirmation of receiving a permission for entering the next sector.

In the CTS part of the system, the robot controller manages the movement of the robot in a continuous feedback loop respecting two rules:

following the mission path while keeping the maximum distance from the path within the predefined limit (maximum allowed error) and

not entering a sector if it is not allowed to (i.e. stopping before the contour of the robot passes the end of the current sector).

If the permission to enter the next sector arrives before the robot has reached the end of the sector, a properly chosen path-following algorithm will make it move smoothly to the next sector without slowing down, as in Figure 7. If the robot approaches the next sector and the permission has not arrived, it has to slow down or even to stop and wait for the permission (Figure 8).

Figure 7.

Mission phase with permission received before the decision point.

Figure 8.

Mission phase with permission received after the decision point.

Ensuring the assumed behaviour of the CTS part relies on the implementation of the robot controller, whose design should take into account the dynamics, constraints, and other parameters of the robot.

Low-level procedures

The minimal set of functions that must be provided by a robot in the continuous time part of the system is

path following with a limited maximum distance from the path during the motion,

forward velocity control: acceleration, deceleration, stopping, and constant.

Those system defined requirements may be transformed to the low-level robot functions of

direction velocity control, calculating velocity which will allow following the path and reduction of the tracking error if needed,

longitudinal velocity control, which will change the forward velocity according to the requirements of the robot controller,

localization, providing current position of the robot both to determine path-tracking error for lateral control and to locate the robot with respect to segment characteristic points for the robot controller.

The specific choice of the methods and algorithms that provide these low-level functions depends on the type of the robots and their sensors.

The system we present was developed with the assumption that the robots are based on a general differential drive platform, with two independently driven fixed wheels. It was also assumed that the robots move relatively slowly, so the dynamic effects may be neglected, and the robots are controlled on the kinematic, velocity level. With these assumptions the robot is represented with a unicycle model

\begin{matrix} \overset{\cdot}{x} = v \cos θ \\ \overset{\cdot}{y} = v \sin θ \\ \overset{\cdot}{θ} = ω \end{matrix}

where $(x, y, θ)$ define position and orientation of the robot, $v$ defines longitudinal velocity and $ω$ the angular velocity of the robot.

The components of the system were implemented as Robot Operating System (ROS) modules. ROS environment with its ecosystem accelerates development and increases flexibility of the system to future modifications and enhancements. Using ROS as a middleware simplifies also switching between simulations and physical robots. The implemented architecture allows testing the same algorithms on a group of Turtlebot2-type robots as well as Gazebo simulation environment.

The differential drive kinematic model of the robot allows full separation of lateral and longitudinal control. It can be obtained by defining direction control as the signed curvature $k$ , which is a geometric curvature of the planar curve the robot follows with a positive sign while turning left and negative when turning right. Then the angular velocity applied to the mobile robot becomes $ω = vk$ . It must be noted that such representation does not allow in-place rotation when the curvature becomes infinite; however, in the system described it is not required and in general the issue can be solved by a special case for zero forward velocity.

The problem of lateral control of a mobile robot was a subject of numerous research papers leading to several algorithms that can be used for this purpose, such as pure pursuit, Stanley, sliding-mode based, or model predictive. A recent review of these algorithms may be found in Tagne et al. (2016) and Dominguez et al. (2016).

In our system we have selected spline-based modification of the pure pursuit algorithm. The pure pursuit (Coulter, 1992) is probably the most common algorithm of the lateral control. The original version defines a motion curve as a circle between the current robot position and orientation and a point on a path in a look-ahead distance $d$ . The drawback of the approach is that while at the starting point the orientation of the robot matches the orientation of the followed circle, at the look-ahead point the tangent to the circle and to the original path do not match, which leads to overshooting and oscillations around the path. The spline modification does mitigate this problem, as the proper orientation of the robot is set in both initial and final point of the spline.

Given robot position $(x, y)$ and direction $v_{t} = (\cos θ, \sin θ)$ and a path segment to be followed $p (s)$ with length parameterization the lateral control algorithm is then defined as

find the point on a path closest to the robot

s_{t} = \arg min_{s} dist ((x, y), p (s)),

determine look-ahead point $p_{d} = p (s_{t} + d)$ and tangent in that point $v_{d} = dp (s) / ds |_{s = s_{t} + d}$ ,

find a cubic spline connecting parameterized by boundary conditions $((x, y), v_{t}, p_{d}, v_{d})$ ,

use the current curvature of the spline as the lateral control of the robot.

The longitudinal control of the robot is calculated as a function of current and expected velocity of the robot and the robot acceleration constraints.

The localization component of the system is assumed to provide the position of the robot with a known, limited error. The precision of the localization module together with the maximum error of path tracking determine minimum value of sectors’ margins. The realization of the localization may differ depending on available sensors. The developed system uses various approaches to localization: in simulations one can test the system with either exact position obtained from the simulator or the position with added random noise. When using physical robots there are two configurations available, the first using a motion-capture system with high precision, and one based on Decawave radio localization modules with bigger localization errors, but covering a larger motion area.

Illustration of the proposed control – a simulation example

To illustrate the operation of MMRS under the proposed control, a simulation system has been developed. Figure 9 presents a screenshot of the animation¹ of eight robots sharing a common motion area. Each of the robots follows independently its specified path partitioned into sectors. Figure 10 depicts these paths and an enlarged paths’ fragment with marked sectors. As mentioned earlier, the discussed supervisory control accepts any path partitioning; however, it is advantageous to minimize the length of the conflict sectors. The state of each robot is represented in a discrete way by the sectors it is currently occupying. The supervisor follows this state through the feedback from the robots (observable events) and prevents the system from reaching the states leading to collisions or deadlocks (through controllable events) according to the proposed PN model and the discussed DAP. The coordination mechanism is independent from the velocity profiles of the robots, whereas the efficiency of the system measured by some time criteria (e.g. completion time of all robots’ missions) may differ depending on the assumed priority policy. In the presented example, the conflicts are resolved using the FIFO rule.

Figure 9.

A screenshot of computer animation of a group of robots sharing the motion area.

Figure 10.

The paths of the robots (left) and an enlarged fragment showing the path partitioning (right).

Conclusion

The paper contributes with a hybrid control system for MMRS that comprises the supervisory control level, based on a discrete event model of MMRS, and the robot control level, based on a continuous time model of the robot motion. The proposed supervisor formally guarantees the required logic of the system behaviour, that is, collision-free robot motion and correct completion of their tasks, whereas the robot controllers ensure realization of this logic by the robots.

The modular construction of the hybrid control system provides for its modification and experimental examination of the impact of different structural and algorithmic solutions on the efficiency of sharing the common motion space. The factors that can be considered in the optimization of MMRS operation include different ways of discretization of the continuous MMRS model (paths partitioning, space partitioning) and conflict-relation construction, multi-level collision-avoidance policies, collision avoidance through path modification and/or velocity modification, various approaches and algorithms for deadlock avoidance, and various approaches and algorithms for robot prioritizing.

The proposed control concept is underway, its implementation in a testbed for a group of Turtlebot robots. This provides a framework where the above-mentioned aspects may be tested both in simulations and in experiments with real robots. Apart from the factors related to the discrete-event level of the system control, the framework allows verification of issues related to the real-time motion such as, for example, influence of the robot positioning precision and the communication packets loss on the system performance. The former affects the system efficiency through the requirement of a different division of the paths to sectors. The latter introduces additional unpredictable delays of robot responses to supervisor commands.

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 the National Science Centre, Poland, under the project number 2016/23/B/ST7/01441.

ORCID iDs

Elzbieta Roszkowska

Janusz Jakubiak

Notes

References

Andreasson

Bouguerra

Cirillo

, et al. (2015) Autonomous transport vehicles: Where we are and what is missing. IEEE Robotics and Automation Magazine 22(1): 64–75.

Basilico

Gatti

Amigoni

(2009) Leader-follower strategies for robotic patrolling in environments with arbitrary topologies. In: Proc. of The 8th Int. Conf. on Autonomous Agents and Multiagent Systems, AAMAS’09. pp. 57–64.

Cap

Novak

Kleiner

, et al. (2015) Prioritized planning algorithms for trajectory coordination of multiple mobile robots. IEEE Transactions on Automation Science and Engineering. 12(3): 835–849.

Coulter

(1992) Implementation of the pure pursuit path tracking algorithm. Technical Report CMU-RI-TR-92-01, Carnegie Mellon University, Pittsburgh, PA.

Dominguez

Ali

Garcia

, et al. (2016) Comparison of lateral controllers for autonomous vehicle: Experimental results. In: 2016 IEEE 19th International Conference on Intelligent Transportation Systems (ITSC). pp. 1418–1423.

Ferrera

Capitán

Castaño

, et al. (2017) Decentralized safe conflict resolution for multiple robots in dense scenarios. Robotics and Autonomous Systems 91(5): 179–193.

Ferrera

Castaño

Capitán

, et al. (2013) Decentralized collision avoidance for large teams of robots. In: 2013 16th International Conference on Advanced Robotics, ICAR 2013, pp. 1–6.

Inalhan

Stipanovic

Tomlin

(2002) Decentralized optimization, with application to multiple aircraft coordination. Proc. of CDC02. IEEE. pp. 1147–1155.

Krzykala

(2021) Student project: animation illustrating the mmrs control concept. https://drive.google.com/file/d/15Iex10AmcqQBQcnGucGgxujePiukWtNY/view?usp=sharing.

10.

La Valle

Hutchinson

(1998) Optimal motion planning for multiple robots having independent goals. IEEE Transactions on Robotics & Automation 14: 912–925.

11.

Lygeros

Godbole

Sastry

(1998) Verified hybrid controllers for automated vehicles. IEEE Transactions on Automatic Control 43: 522–539.

12.

Pallottino

Scordio

Bicchi

, et al. (2007) Decentralized cooperative policy for conflict resolution in multivehicle systems. IEEE Transactions on Robotics 23: 1170–1183.

13.

Pecora

Cirillo

Dimitrov

(2012) On mission-dependent coordination of multiple vehicles under spatial and temporal constraints. In: Proc. IEEE/RAS Int. Conf. on Intelligent Robots and Systems. p. 52625269.

14.

Reisig

(1985) Petri nets. An introduction. Springer-Verlag.

15.

Reveliotis

Roszkowska

(2011) Conflict resolution in free-ranging multivehicle systems: A resource allocation paradigm. IEEE Transactions on Robotics 27(2): 283–296.

16.

Roszkowska

(2005) Provably correct closed-loop control for multiple mobile robot systems. In: IEEE Int. Conf. Robot. Automat., ICRA’05. pp. 2810–2815.

17.

Roszkowska

Dulewicz

Janiec

(2018) Coordination of concurrent mobile robot motion processes with composite automaton supervisor. In: 23rd Int. Conf. on Methods & Models in Automation & Robotics (MMAR), pp. 785–790.

18.

Roszkowska

Dulewicz

Janiec

(2019) Hierarchical hybrid control for multiple mobile robot systems. IFAC-PapersOnLine 52(8): 452–457.

19.

Roszkowska

Jakubiak

(2020) Testbed for control synthesis for multiple mobile robot systems: General concept and current research*. In: 2020 7th International Conference on Control, Decision and Information Technologies (CoDIT), volume 1. pp. 1179–1184.

20.

Roszkowska

Reveliotis

(2013) A distributed protocol for motion coordination in free-range vehicular systems. Automatica 49(6): 1639–1653.

21.

Tagne

Talj

Charara

(2016) Design and comparison of robust nonlinear controllers for the lateral dynamics of intelligent vehicles. IEEE Transactions on Intelligent Transportation Systems 17(3): 796–809.

22.

Tomlin

Pappas

Sastry

(1998) Conflict resolution for air traffic management: A study in multiagent hybrid systems. IEEE Transactions on Automatic Control 43: 509–521.