Project topics and materials
Get Complete Project Material File(s) Now! »
Invariance of the priority graph
If previous work already noticed the existence of homotopy classes in multi robot coordination, to our knowledge, no meaningful representative is proposed to encode homotopy classes. In the following, we present the main result of this part: priorities uniquely encode homotopy classes of feasible paths in the coordination space. The existence of a nite number of homotopy classes thus merely appears as the consequence of the nite number of possible priority graphs. We let ((free)) := {(‘) : ‘ 2 (free)} denote the set of values taken by the priority graph over all feasible paths. ((free)) is a subset of G containing graphs G such that there exists a feasible path ‘ 2 (free) satisfying (‘) = G. The following theorem (illustrated in Figures 3.3 and 3.4) shows that priorities and homotopy classes are strongly linked: more precisely, there is a bijective relationship between homotopy classes and « feasible priority graphs » (this term will be precisely dened in Section 3.2). We say the priority graph encodes the homotopy class.
Sucient condition for priorities feasibility
The above examples tend to indicate that no deadlock can occur under acyclic priorities. It is not surprising as deadlocks usually involve a « circular wait » [24]. In many circumstances, imposing acylic priorities is not a problematic constraint and demonstrates some benets including deadlock avoidance (see Part III). That is why we start by providing a sucient condition for priorities feasibility stating that acyclic priorities ensure deadlock avoidance.The proof of the above theorem relies on the fact that under acyclic priorities, a simple feasible path respecting the acyclic priorities can be constructed by letting robots go through the intersection one by one.
Proof. Take an acyclic priority graph G 2 G. To prove that G is feasible, we are going to exhibit a particular feasible path whose induced priority graph is G. As G is acylic, it admits a topological ordering of its nodes R. Consider a relabeling of robots along this topological ordering, i.e., robot 1 is the maximal element of this topological ordering, … robot i is the ith element of the topological ordering, … and robot n is the minimal element of the topological ordering. Consider the path ‘ constructed as follows. ‘(0) := xobs and for all i 2 {1 · · · n}, within time interval [(i − 1)/n, i/n], robot i moves forward from xobs i to xobs i (for example ‘i is linear in that time interval and takes values [xobs i , xobs i ]) while other robots j 6= i do not move (‘j constant in that time interval). This path is feasible and takes values in free G .
Note to the reader The two following subsections intend to treat the case of cyclic yet feasible priorities. They are quite technical and the reader having no particular interest in this case can go directly to Subsection 3.2.4. It will not aect the understanding of the rest of the thesis.
Characterization of feasible priorities
Before providing a formal characterization of feasible priority graphs, a geometric interpretation is provided about why in certain circumstance cyclic priorities are not feasible. In Figure 3.10, the obstacle cylinders in the coordination space are depicted for both the cyclic deadlock-free example of Figure 3.7 and the deadlock example of Figure 3.6. The main dierence is that in the deadlock case, cylinders intersect with each other. In contrast, in the deadlock-free case, cylinders do not intersect each other, there is a certain distance between each cylinder. Thanks to this distance between cylinders, the multi robot system can decide, independently for each collision cylinder, on which side to travel. On the contrary, if there is not a sucient distance between cylinders, theses decisions are not independent. It is very clear on the right drawing of Figure 3.10 that if a feasible path lies above the obstacle cylinder obs 23 (the blue one) and below obs 13 (the red one), then it also must lie on the right relative to the obstacle cylinder obs 12 (the cyan one). In terms of priorities, it means that if 3 2 and 1 3, then we must have 1 2, i.e., the cycle 2 1 3 2 is forbidden.
Table of contents :
Abstract
Acknowledgment
1 Introduction
1.1 Industrial motivation
1.2 Plan or react ?
1.2.1 Planning as a generative mechanism of action
1.2.2 Intelligence without planning
1.2.3 Plan as a resource to guide action
1.3 Contributions
I Priorities: denition and properties
2 Priorities: a geometric concept in the coordination space
2.1 The coordination space approach
2.2 The priority relation
2.2.1 The completed obstacle region
2.2.2 The priority relation
2.2.3 The priority graph
3 The coordination space under assigned priorities
3.1 Priorities: a homotopy invariant
3.1.1 Homotopy classes
3.1.2 Invariance of the priority graph
3.2 Feasible priority graphs
3.2.1 Sucient condition for priorities feasibility
3.2.2 Safety margin
3.2.3 Characterization of feasible priorities
3.2.4 Absence of deadlocks
II Priority preserving control
4 Priority preserving control in the absence of inertia
4.1 A monotone control system
4.2 The proposed control law
4.2.1 Priority preservation
4.2.2 Optimality
4.2.3 Liveness
5 Priority preserving control under kinodynamic constraints
5.1 A monotone control system
5.2 The proposed decentralized control law
5.2.1 Priority preservation
5.2.2 Robustness
5.2.3 Liveness
6 Robustness with respect to bounded noise
6.1 Control model with bounded noise
6.2 Evolution of the non-deterministic information state
6.3 The proposed decentralized control law
6.3.1 Priority preservation
6.3.2 Robustness
6.3.3 Liveness
III Priority-based coordination
7 Overall priority-based coordination system
7.1 Three-layer architecture
7.1.1 The intersection controller
7.1.2 The behavior-based layer
7.1.3 The sequencer
7.2 Priority assignment
7.2.1 A simple priority assignment policy
7.2.2 Request processing liveness
7.2.3 Stability guarantees
8 Simulations
8.1 Implementation aspects
8.2 Simulation results
8.2.1 Simulations under deterministic control
8.2.2 Robustness regarding unexpected deceleration
8.2.3 Robustness regarding bounded uncertainty
8.2.4 Stability guarantees under back-pressure control
Conclusions and perspectives
Bibliography
