Cooperative control of 3D mobile agents with limited sensing capabilities

(1)

Problem definition Mathematical framework Statement Proposed algorithm

Cooperative control of 3D mobile agents with limited sensing capabilities

Preliminary discussion

Stefano Falasca

May 3, 2010

(2)

Prof. Ing. Andrea Caiti

Dott. Ing. Emanuele Crisostomi

Dr Guy-Bart Stan

(3)

Goal Assumptions

The objective of this work is to devise an algorithm that, when executed by a group of vehicles, makes them move towards a configuration exhibiting the following properties:

I allows agents to sense a given target-point;

I allows agents to cooperate.

(4)

(5)

Goal Assumptions

Vehicle

(6)

Sensing

(7)

Goal Assumptions

Environment

I Contains massless agents;

I does not contain obstacles;

therefore

I no need for obstacle avoidance;

I no collisions among agents are possible;

(8)

Agent definition

An agent is a 5-uple of real numbers A = (x , y , z, φ, θ) such that:

I φ ∈ (−π, π]

I θ ∈0,^π₂

(9)

Sensing agent

Leading structure and algorithmic issues

Agent definition

A = (x , y , z, φ, θ)

I pA= (x , y , z)^T is the position of the agent;

I i_A = (cos(φ) cos(θ), sin(φ) cos(θ), − sin(θ))^T is its sensing axis.

(10)

Cone definition

A cone is a 6-uple or real numbers C = (x , y , z, m, M, α) such that:

I x²+ y²+ z² = 1;

I 0 < m < M;

I α ∈ (0, π]

(11)

Sensing agent

Cone definition

i_C = (x , y , z)^T is the cone axis.

(12)

Sensing agent

The definition of sensing agent gathers together the agent and the sensing parameters.

Proposed task: a generalization of rendezvous.

(13)

Sensing agent

Sensed information

The information sensed by a sensing agent are:

I its own position and attitude at every time;

I the position of a certain (time-varying) set of agents;

I an identifier for every sensed agent.

(14)

Connection maintaining strategy

Maintaining the connection among agents is considered to be an hard constraint¹ within this work.

Roadmap:

I limited sensing capabilities;

I existance theorem;

I a convex approximation of the feasible region.

1e.g. Notarstefano.

(15)

Sensing agent

Connection maintaining strategy

Limited sensing capabilities

I M1− M₂ = m2− m₁ = ρ

I m2

2 (cos (α₂) − cos (α₁)) = ρ

(16)

Connection maintaining strategy

Existance theorem

Theorem

Given an agent A₁ beeing sensed by a sensing agent A₂ there exists a sensing agent ˆA2: kpAˆ2− p_A₂k ≤ ρ such that every agent Aˆ1 : kp_A_ˆ

1− p_A₁k ≤ ρ is sensed by ˆA2.

The introduction of the ρ-limited sensing region has led to the ability of independently² evaluate the connection-maintaining set.

2first-order agents (e.g. Bullo), second order agents (Notarstefano); both using disk sensors.

(17)

Sensing agent

Connection maintaining strategy

A convex approximation of the feasible region

I δ : kδk ≤ ^{min{ρ,d −m}ⁱ}−max{−ρ,d−M_i} 2

I t = max{−ρ,d −Mi}+min{ρ,d−m_i} 2

I (x , y , z)^T = p_A₂+ t^p^A1^−p_d ^A2 + δ

I φ = arctan2(pˆ y, px)

I θ = arctanˆ

−√ ^p^z

(p_x²+p²_y)

h i

(18)

Rendezvous of subsets of vehicles³ during flocking.

Degrees of freedom (β, γ and δ) are not exploited.

3the same happens when using the so called averaging control and communication law; connection is not maintained.

(19)

Sensing agent

Leading function

The leading function is a map ldr : [1, . . . , n] × N → [0, 1, . . . , n]

such that:

I ∀ k ∃! i : ldr(i , k) = 0;

I ldr(i , k) 6= i ,

I ldr (ldr (i , k) , k) 6= i ,

I . . . ,

I ldr (ldr (. . . ldr (i , k) . . . , k) , k) 6= i , . . .

(20)

Algorithms

Computation

An algorithm is a set of sequences n

{dcs_A_i(k)}_k≥0|A_i ∈ Ao

; where dcs_A_i(k) = (A_i(k + 1) , ldr (i , k + 1))

(21)

Sensing agent

Algorithms

Functional dependencies

(22)

Algorithms

DAG⁴

Model for robotic networks that communicate, process information and move at discrete time instants.

4comes from the branch of parallel computation.

(23)

Sensing agent

Algorithms

Dynamical, distributed generation of the leading function

1. dashed lines shall only connect agents being in visual contact (i.e. the dashed edge ((j , k) , (i , k + 1)) is present only if agent i senses agent j at time k);

2. ldr(i , k + 1) will be choosen among the incoming dashed lines for the DAG’s vertex (i , k).

Choose a set of dashed lines connecting agents on a stage (k − 1) ÷ k DAG such that however we choose one incoming

(24)

Algorithms

Dynamical, distributed generation of the leading function: example

The so called floodmax algorithm can be casted into this framework.

(25)

Pair visibility problem Gram matrix

Pair visibility problem

Sensing both the target and the leader

(26)

Pair visibility problem







m ≤ kv₁k ≤ M

m ≤ kv₂− v₁k ≤ M

−2α ≤ θ ≤ 2α

. (1)

(27)

Pair visibility problem Gram matrix

Problem statement



 v₁ . . .

v_n





v1 . . . vn = G = {G_ij}

The conditions become—apart from m ≤ G_ii(k) ≤ M ∀i :





m ≤ pG_ii(k) + G_jj(k) − 2G_ij(k) ≤ M pG_ii(k) + G_jj(k) − 2G_ij(k) cos(2α)+

(28)

Approximate Gram matrix analysis

G₁₁ G₁₂ G12 G22

=

kv₁k² v₁^Tv₂ v₂^Tv1 kv₂k²

I G22 is given

I the Gram matrix respects the stated conditions for the goal to be achieved

I given a solution to the current problem { ˆGij} = ˆG , the same problem can be solved if G₂₂= ˆG₁₁

Recursivity

(29)

Concept

(30)

DAG representation

(31)

Cooperative control of 3D mobile agents with limited sensing capabilities