Robot intelligence in natural environments

Translation of description of equivalent WO 02082195 A2

cυ O r IV) P-¹ P¹

Cπ O Cπ o π o cπ

<img file="WO02082195A2_D0001.tif" />

In another method, which also eliminates the need for a communication network between the robots, the robots are equipped with sensors that can detect other robots within a certain range. Whenever a robot detects another robot, the potential collision point of the robot is calculated and the trajectory changed accordingly to avoid the collision. However, since replanning the trajectories is done on a local basis, this can lead to mutual blockages of the robots (see below) that are not captured and resolved. Such a method is described, for example, by L. Chun, Z. Zhang and. Chang, A Decentralized Approach to the Conflict Free Motion Planning for Multiple Mobile Robots, "Int. Conf. On Robotics and Automation (ICRA), pp. 1544-1549,

A different approach is followed by methods in which a coordination of the movement paths takes place by means of a central component. Basically, there are two possibilities, namely that the central component creates collision-free trajectories simultaneously for all involved robots; On the other hand, it is possible that mutually independently planned trajectories of the robots are only subsequently coordinated by using the central component. The first method is described, for example, in J. Barraquand, B. Langlois and J.-C. Latombe "Numerical Potential Field Techniques for Robot Path Planning, IEEE Trans. On System, Man and Cybernetics, Vol. 22 (2), pp. 224-241, 1992. An example of the second method is described in S. Leroy, JP Laumond and T. Simeon " 8th International Symposium on Intelligent Robotic Systems (SIRS), 2000. A disadvantage of all methods which use a central component for the coordination of the trajectories, however, is that they require a global communication network between the robots. Moreover, these methods are computationally complex and inflexible. 8th International Symposium on Intelligent Robotic Systems (SIRS), 2000. A disadvantage of all methods which use a central component for the coordination of the trajectories, however, is that they require a global communication network between the robots. Moreover, these methods are computationally complex and inflexible.

Easier and more adaptable coordination among robots with a less complex communication network could be achieved by decentralized algorithms where only communication between pairs of physically close robots takes place.

The object of the present invention is therefore to specify a method for the decentralized coordination of the movement paths of a plurality of mobile robots communicating with one another within a given spatial area to avoid collisions, as well as for the detection and resolution of mutual blockages, with which the disadvantages of the known Procedure can be avoided.

This object is solved by the features of the independent claim of the present invention. Advantageous embodiments of the invention are specified in the subclaims.

According to the invention, a method is provided for the automatic, decentralized coordination of independent, segmentable movement paths of a plurality of mobile robots communicating with each other within a predetermined spatial area, for avoiding collisions, as well as for detecting and resolving mutual blockages, which is characterized is that:

a robot receives position information from the other robots and its spatial distance (i.e._rob) to the other robots, - a robot falls below a predetermined distance (i.e._Sic_He_r) to the other robots each creates and maintains a coordinating connection to these robots for coordinating its trajectory with the trajectories of the other robots as long as the predetermined relative distance is undershot, one of the robots connected by one coordination link being selected as the coordinator and the other as the partner .

a coordinator requests the planned trajectory segments of its partner and initiates a collision avoidance algorithm by which the trajectory segments of the partner are aligned with its own trajectory segments to determine collision areas where the robots maintain a predetermined minimum distance (i.e._min), and wherein a temporal sequence scheme for the trajectory segments of coordinator and partner is determined,

a coordinator assigns permission to execute the next trajectory segment based on the scheduling sequence for the trajectory segments of the coordinator and partner and executes the trajectory segment only if permission is granted,

a robot for detecting a circle of mutually blocking robots initiates an algorithm for blocking detection if it has not been granted permission to execute its next movement path segment,

upon detection of a circle of mutually blocking robots, a blocking solution algorithm is initiated by the detecting robot, comprising a first step and a second step, the first step being that, in a coordinating connection of the mutually blocking robots, the order of execution the second step is that one or more of the robots belonging to a circle of mutually blocking robots reschedule their trajectories, the second step being performed only when the robot traverses the next trajectory segment of the robot connected by a coordination link first step did not lead to any blocking solution.

This will now be explained in detail. In the method according to the invention, each robot is capable of communicating with all other robots and exchanging information about the respective location when the other robots are within a certain predetermined spatial distance from it. Each robot evaluates the location information received from the other robots and determines the spatial distance between it and the other robots. (In any case, any inaccuracy between the distance calculated from the location information given by the other robot and the actual distance between the two robots should be less than δd.)

If the distance determination of a robot shows that to be as d_rob denoted distance to another robot smaller than one as d_sι_Cher designated predetermined minimum distance, minus the possible inaccuracy δ_d, d_rob - δd &lt;d_siThen this robot initiates a coordination connection to this robot. This coordination connection is maintained as long as the predetermined minimum distance between the two robots is exceeded. Each robot can simultaneously initiate and maintain several coordination connections to other robots if the predetermined minimum distance d_sic_He_r falls below these robots is.

The task of a coordinating connection between two robots is to control the movements of two robots along their movement. Cü ω [NJ r

Cπ o cπ 0 Cn O Cπ

rt H3 P3 N φ tr K ≤! tr Z. N s: PP tr P! cn K cn *^■, tr CΛ P. α &lt;! t J -^r LP P LP

P- φ φ p HPP P-PP φ P φ φ φ PPO Ω P-φ φ PP φ P-φ φ Z φ P φ P o cn p&gt; Ω 3 p-cn P n tr lP H tr O tr φ P | Λ tr PPP 1 H- LP PPP pf Φ o K p- p Φ rt p P &lt;cn PP φ P 3 -¹ P 3 P φ tr cn rt ιp LP o cn Ω φ rt φ N φ ω φ φ n od O cn CΛ P 3 PP φ ω cn φ rt P Ω cn! cn o N φ P- P rt P φ &lt;! N φ P P- φ P "φ φ p- PP P- P φ POPP tr tr φ tr

Hi PP rt - Φ P- o Φ P • Ω P s: Ω L p- P cn φ rt N ^ p rt PP φ PPP

PP * P¹ rt P H-3 tr P φ tr 3 PP Hi CΛ Φ φ 3 Φ CΛ Φ P tr 3 tr

[-3 O Ω - rt O r- rr rt φ P. _^ P LP φ φ φ rt: φ φ H-φ tr PP H-P, 1 tr ü P3 p P-φ P P-PP 3 OPP rt P n φ ^fr Φ N Φ Φ o T) *_* φ 0 z Ω P-rt PM Qr PM rt P 3 od O P rt φ cn PP z φ Qr P

Φ 0 s: p- ^ tr H Φ P Φ iP ^frd α P- φ P P- φ P- rt P φ P- φ

P3 p &lt;! OPH o φ tr φ 3 cn P¹ Qr PP P rt s; Ω P P rt Pύ P- PP cn o P- o 3 P Qr o PP Hi P tr P φ PP φ rt φ «tr 3 φ P 0 φ 0 tr N 'S p"_"»P H rt Φ P P. PPP rt Qr Φ PO 1 P- P 3 Φ tr l_l. cn ≤ o •_^ o P &amp; rt CΛ ^ tr 0 t tr P öd -¹ POP rt rt P 0 φ φ N rt cn w P P- Hi φ • d P 0 PP φ φ&gt; T} φ rt PP: Dd rt Z PJ li P

₌ cπ P- Hi φ P o P φ P- P P- P- PP s: lp cn φ Z LP φ φ O Qr g ö _^ rt Hi PPP^J P- P cn Qr P cn LP Φ P CΛ P- 3 Φ Z. P Φ P P -tr -T

P φ P- P rt LP fc Ω P- P- φ W rt φ P φ tr PH P- φ P z P -¹ 0 P 0 p P no Ω P o φ cn tr φ NP Ω P. PPPPPPP P- P iP α p: cn rt • 0

P- p. Ό p P- PP cn P rt g P tr P Φ Φ P tr et Ω Φ P Φ tr φ P w Φ Hi Ω Φ M 3 rt rt PPPP LP PO tr PP ^_* P- PH fid Qr po •_^ PP tr cn cn POHP • cn O cn P ip rt PP cn P P- o -J rt PP φ rt OP¹ PPP od tr tr O Φp: Φ O Hi • PPP

P? &gt; Φ P 3 P 3 P pj: ~ - P φ P * 1 PP ιQ P tr P- tr O Ω P- for P- rf- 1 1 tf Pl p PP^J P- P Ω cn P £ P- 0 tr P 3 P φ ιp PP 3 φ tr P rt φ o fr] a φ H Tl rt tr tr O LP cn φ CΛ PP H- φ P φ tr P P- p P p PPP Hi PP cn φ LP rt cn PP φ PP φ Ω P φ φ cn φ cn φ Pt LJ. PP p: P Φ P- rt Φ Hl PP Qr P φ P rt • x) P- Φ P tr φ P- P- Ω P

Φ p Φ tr rt P LP P- ω Φ P p: p: PPP ig rt Φ PPPP rt Qr PPP tr _^Pp rt Ω φ PPP tr Ω LP cn POP cn P φ φ φ φ

H p Ω Φ rt P- Φ 0-Qr Φ Hi PP tr cn Φ Φ PP rf rt Dd P- 3 PP ^' pp ∞ PO rt P P- Φ P p: ω P rt cn tr l_ |. PPP P-Φ P P-P, ZP rt P.⁽ ) PP Φ Φ PH Φ P rt P Φ rt rt Φ CΛ φ 3 Z. P φ Φ cn O &amp; φ CΛ

_* P ^ P 3 P- s; s: Φ tr ≦, Φ Φ P- P 3 Φ P cn P- 0 Hi pn cn op rt P- CΛ K Φ Φ P Φ P- P? Φ LP Φ PP, PO tn o O p P- Tt &lt;! rt φ P 3 P LP φ P Dd P- P- 0 PPP LP P φ 0 P φ «o P- OO rt LP Hi cn P 3 P. φ p. rt Φ NPPP-P 0 P-LO p PPP Φ 3 P-Jö P φ s: P cn P Φ Hi Φ LP φ &lt;PP Φ Z

Hi P- i) p φ POP LP πd PP P- P- P- LP cn P- OPP P- p- P^J cn &lt;HP ^ CΛ P P. tr f_ι: cn P LP Ω P φ öd rt φ Dd σ Ω P φ P- φ &lt;P P- p- O P- rt P o Ω tr PP 'p&gt;: P Φ ( - • P- Hi Φ P tr PPP 0 p.cn

OO ^ p P φ φ P rt tr P rt α PN Ω s: P- φ P rt tr rt cn PPP P- pp P LP ^ P- L φ CΛ tr PP LP P tr P. φ Ω PPP φ pr rt P P.O.

1 PPPP rt P φ tr cn Hi cn OP tr φ P- LP cn P- 0 O LP 01 PP

PJ ^ o PP φ φ cn φ ω P φ σ P- rr OP φ P φ P φ P- P tr P cn φ tr φ o PP^J ι-3 rt cn P P- P φ P- P tr φ PP cn PP LP φ φ 0 &lt;ιQ φ P tr φ α tr φ P ω lQ tr P r LP LP 3 ω 3 rt P φ 3 H- o φ OO φ P&gt; 03 tr Hi φ 3 O; v P φ öd p-cn P s: cn φ φ φ PP φ N rt p Hi PP¹ Φ rt φ s: φ P cn P φ P tr tr φ φ σ P&gt; x) PP r P z

P op P P z P φ P φ P φ SPP Hi 2; 1 P rt Dd P P rt Φ P-

Φ o φ P3 P o φ LP rt n P LP φ rt tr O φ P tr φ φ PPPP φ P. cn no O rt CΛ P φ P o φ P 3 0 LP OPP φ PPZ rt φ P φ Ω n P^J tr. P- P p LP P φ tr φ φ tr PP φ LP rt P 1 φ P cn PP tr

P P- O 1 rt P rt LP P Φ PPPPP Φ Φ P iP Φ PN Dd Φ p P- p rt s, tr LP Φ cn rt P- rt rt Φ iP cn 1 rt tr P h P. P LP Φ Φ P

PPP P-3 cn p PI Φ p. 1 CΛ H- &lt;! • 2: • POPHZ

PP Ω P 1 P P- Φ Φ 1 Ω O φ iP O 1 1 φ P- 1 CΛ CΛ ω P P- P- tr PP cn P- P 1 tr cn rt 1 1 i 1 Φ 1 1

CO O ΓΌ to P¹

Cπ O Cπ o C 1 o cπ

P φ cn

P cn

Hi p: tr

P

P

P

LP ω

Z φ

LP

CΛ

C o o

P^J rt

Φ

P

P

P

Ω tr

P p φ

P

P rr

Φ

P Λ

Ω

P^J

P- φ

P

P-

Ω tr

Φ

P

P cn

1 <img file="WO02082195A2_D0002.tif" />

co co t I-¹

Cπ σ Cπ o Cπ O cπ

<img file="WO02082195A2_D0003.tif" />

co ot to P¹ P&gt;

Cπ o cπ o Cn o Cπ

rt Φ P rt _ P &lt;P. cn LP PZP CΛ cn P tr Qr X) Φ cn LQ P tr 3 ö &lt;Z i X ü Z td

P P o φ σ φ OP p&gt;: P φ φ PP φ X5 φ φ φ Hi P rt PP o P- P o φ OPP φ

PP 3 3 P- PP φ PP LP Hi PP P- 3 P- P φ rt Φ P Hl P-¹ rt φ PP tr PPO

LQ Φ 3 cn cn N P- LQ LP φ P rt φ P- ω iP P- P o P φ Qr Ω cn φ • »rt&gt; P cn cn P tr φ CTi CΛ P P. Pi) cn φ CΛ φ Pi P rt P- φ WS Pi PPP LQ φ cn PP φ cn P φ o φ PP cn P- P- P- O P- φ φ P t * P-

Hl o S P- tr Cn PO φ rt tr P- ZPP tr φ P φ P φ PO φ P- PZ φ Φ

Φ os; P tr φ ZP φ P P-3 P φ φ o CΛ Ω Q LQ φ P φ P cn P φ P

P- P P- P- P P- φ PP rt tr p: o P- P rt tr 3 P rt PP φ cn P LP P

P¹ P rt LP P P P P C Λ Dd cn φ P φ P- Φ P- 3 S Φ P φ 3 P

P-PP¹ Φ φ cn NQ φ LP rt CΛ φ φ P cn P r P cn PP Pi P o P- LP LP φ PL £&gt; α P φ P φ LP • • φ P- ZH o rt r P &lt;P- P- Φ tr P φ φ Q - φ p P - co H) P φ P φ φ 3 P i: P - P φ Ω φ P - o P - P p - P rt φ tπ o p s: P - P - PS! M h iQ PO tr P P- P P- P H H tr h P rt Dd P cn φ cn P P- Φ O P- P Ω cn P- tr φ P cn tr HP cn tr PPH CΛ rt P Φ φ Φ φ .-&gt; rt P φ PPPP tr φ φ φ tr PP cn o P Hi P- φ cn φ φ PPPZ Pi P- i Qr

PPP tr P- P φ rt P- P P- LP rt P φ P- LQ P tr P LP öd φ O rt o Φ

LQ tr P! - i P φ rt P cn CΛ CΛ cn Pi φ LQ P- P P- φ φ LP Cn P^J LQ Q tr P- tr P

3 CΛ Φ cn o p rt P- PO P -tr OP φ φ LQ Hi t «P &lt;! o φ PO LP o Qr rt P- P- Ω P- φ LP cn P. Ω P tr CΛ PP φ • p: o φ Ω NP rt φ rt φ φ; rg φ P φ tr φ tr¹ tr O φ P tr tr z LP PX

P tr Pz LQ φ φ O

P z PPP * PP rt &lt;P-ro P o φ P CΛ P Dd P Ω

Φ tr P rt Hi Hi Pi P- o LP cn Φ o P P- P p rt rt PP P- φ P tr P "

P- P- P φ n PO Dd P Ω P φ φ PP φ φ φ o LQ φ P. SPP LQ P P os: n

PPP et tr PO • tr P LP P cn tr φ tr H φ tr PP φ tr P Ω φ - 'φ P. Z φ P li O P- P φ 3 KΩ P. X) Pi o NPP P- PPPPPX P-

P tr o Ω P Φ Qr Ω t φ φ P φ φ δ H o rt φ rt s: cn PP ω P H-rt 3

XS P Φ I. p P- P- r PH cn PP 3 Φ φ o Φ P- • P Ω LP cn P- Φ P Φ Φ P

P iQ P- P P- * PP P- φ φ φ φ rt PZ P- PP LQ tl P trφ φ cn lQ Hi HP n

PPO P-Φ PP P-Hl Qr φ h-¹ p. P rt P rt 3 PH rt 3 P tr CΛ

PM Hi P_φ P cn cn rt P φ LQ CΛ P- P- φ P HI φ z P P- φ

3 OPPP P- cn Φ P- PPPSPPPPPNPPPP LP PP

Φ P cn P- LQ PP Ω P- P- LP cn Φ P P- P- P α PP cn P rt P

P¹ rt POP LP tr Ω P LQ P ^ LQ rt φ p- P cn z

3 N Ω Pncn P φ P

P φ SP LQ φ rt r φ Hi CΛ NP φ φ o PP tr cn PP φ φ p- P

P Φ &lt;! n P- P- cn P Od Z Pi φ tr φ P P- ω! Ω P Φ PP ι-i P Hi

P 3 OS cn rt &lt;P- Φ Φ p: O P- PP P- i Ω cn φ Φ tr P cn cn LQ

LQ Φ P^J P tr Φ Ω P- Z p- tr tr LQ LQ p- P P- P- Φ P LQ 3 Pi Φ Φ

Pi P P "P P 3 PP t φ φ POP φ cn φ o φ LP PP P φ φ PO rt Hl

P- o φ PP tr P LP rt rt P CΛ P &lt;rt tr φ φ PP Hi cn tr NP

P tr φ 3 PP cn P- P P- Pi P tr φ P φ P- φ i φ cn P- PP P. P- P cn o φ P p- o P- PPPP cn o P φ tr P cn Ώ Ω POP ^ Λ Φ t t t tr tr tr tr tr tr tr tr tr tr tr tr tr tr P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P n P n P n Hi Hi. P P P P P P P P P P P P P rt σ φ φ rt P- OP e PP P- pttr PNP

P- PP Hi P¹ PPP rt tr φ • tr P φ P rt φ o P- P Ω PS φ φ P- P φ -&gt; PO • Z LP φ tT φ P rt rt rt P φ P φ n tr o PP tr CΛ PP

P tö PP φ φ PP tr P ö P φ PP P- CΛ n rt tr rt φ PPXP rt P^. P- iQ s PPPPPP P- H ω P- P ö cn φ P o • P rt φ PO: P φ on PNP cn Hi φ rt tr CΛ Q &lt;! P Ω P Φ P rt P- P

P 3 tr Dd O φ LP P- φ φ φ P LQ rt φ φ P tr P-LP φ NP φ P tr

P rt φ 3 m rt φ φ φ P-Pi P rt φ PP n φ cn P cn PPZ P- Φ Φ

PN Ό P cn P P ro 3 P o • LQ tr rt Φ SP p- PPP cn

Φ PPP CΛ Ω rt P Φ P tr Φ &lt;P- Φ o P- Pi Hi z PP rt Φ

-P-¹ P LQ LQ rt cn P tr φ PPP o tr Dd PO z PP^J PPO Φ XP Qr P. I. P- p: Φ Φ ZP rt P rt P- φ p: P o P tr P- 0: P φ φ rt

P tσ HI LQ 1 P o φ MP φ φ cn P- σ P tr φ P 1 Dd o P rt Qr P rt P-

LQ P-p: φ cn PPPPP 1 φ P φ PP φ rt P φ P φ φ Q cn Ω P 1 CΛ P CΛ P-Hl co PPP H-P LQ Z φ cn φ PPPP rt tr P φ φ P cn. fc&gt; P- iQ Φ φ HPP

1 cn Hi PP cn 1 Φ P 1

1 Φ 1 1 1

co o to ro P¹

Cπ O cπ O Cn o Cπ

<img file="WO02082195A2_D0004.tif" />

co co to to P¹

Cπ o Cn o Cπ O cn

Pi πd P φr cn P Pi Sl φ z P g P-¹ Φ N φ P3 P P rt P tr

P CΛ PP CΛ o tr Φ 9 ^ cn P Pi rt tr LQ P. Ω Pi LQ o P P- PP P- P- O φ P- P- P 3 P- P 3 P- o P o PP φ P- fX P φ o P Ω cn Hi PP φ o PPPPP 3 φ CΛ cn rt P φ z LQ iQ H cn tr φ tr tr φ P- φ P

P rt p rt PPPP φ PPP tr P- PPXP φ φ • Ω cn o rt P φ φ p-cn <img file="WO02082195A2_D0005.tif" />

PP rt Φ P- PPP Φ rt CΛ P- 1 P p: t iQ tr tr r Φ cn P Pi H cn Φ

P- φ LP PP P- φ a: &lt;φ PP rt rt Ω o tr tr φ P rt PO φ cn φ P φ P- P-

PP P.P^J φ * i φ LQ P P- p O φ tr OP φ 51 PPP P- P * »Q Ω PP rt

P- P Φ cn PP cn PP P P- NP tr rt 3 PH Φ Ω ZQ cn Ω 3 z tr P p- P- φ tr PPO &lt;rt φ N CΛ PP rt φ s P LQ tr φ Ω ^ tr ! tr φ φ rt Ω LQ

P φ P tr LP φ O Pi PP rt rt φ z PP¹ iQ P- rt PN tr P o φ PPP tr

P z P φ cn φ PP o P LP P- tr φ φ P φ CΛ φ N Qr PZ P. P P- rt Ω P d rt tr

P φ H) Z 3 P tr tr P cn φ φ P&gt; QP rt N CΛ ZP φ φ PP^J P- P tr LQ Hi t-^&gt;

LQ Q 0 P p- P cn o QZH tn φ P rt P P- φ φ PPPP φ P P- P φ LP 3 o cn rt P tr φ Ω P φ rt cn φ rt rt P cn PO H- XP P - cn N P - P Φ PP Φ φ Φ Ω

&lt;P Φ NP tr P. P- φ 3 P- P- Hi Z Pi P rt Φ Ω. -. rt cn tr LP P CΛ P- P- tr; r

Φ zt P- P rt PPP φ cn 3 Cd P Φ 1 P- Φ tr P. P r Φ P- Φ Hi i PO: -i P-

P P o P φ P φ H φ P 3 Ω P "PP σ PP cn PPP P-LP PP o φ CΛ φ tr H 3 φ o rt LQ H φ α φ φ t PPP P- φ rt H φ rt tr P. tr tr P rt LQ P

P- P ω o Φ - P- P &lt;PP Φ P Φ? PP z. -. Ω P φ φ φ tr φ HO • φ φ

P rt £ -i P &lt;! PPO φ - »PP o lQ φ Q Qr tr H P - P φ cn φ rt LQ ω P

P tr ω Qr P- O φ LQ PP rt LQ 3 P tr cn φ φ LP i cn z P φ φ Sl Ω P.

P z Φ HI P- Pi P- PO li cn 3 P Φ φ CΛ P φ o Φ S Pi Φ PP li P-tr Φ

P P- O P- PP o Φ g^: P P. Pi tr P- ZP rt 3 P- P rt N o LQ P- o LQ P- p. P- φ H

LP P tr tr P o P- 3 φ P- φ P 3 rt P XJ o P rt φ tr rt Ω P &lt;Ω O

P rt P tr P. 3 Ω Φ QP Φ P- P LP P. Φ o tr P o tr trn P)

PN 3 P o P 3 φ P. tr P- rt P o XP P- Ω P φ P- P cn rt Z rt Hi P rt φ cn o

3 P LQ PP P- 3 P φ P rt P • φ P tr P Ω tr rt PP s: φ φ. P Φ P Φ tr

LP φ φ φ iP PPPP P- P φ P- Ω P tö tr φ P φ P Pi φ PPPP rt φ P o φ PP tr P- P- tr P φ PP tr P o φ P^J Φ rt o P- P Cd P φ P- rt cn PPP φ P LQ LQ LQ PP φ α φ tr P rt P t- &lt;O CΛ P φ P CΛ iQ P rt P- φ

P i rt P φ P φ φ CΛ φ Dd cn φ PPP φ o φ P- P φ P-PP P-tn cn P

Φ P- -QPPP P- tr 3 cn P- CΛ PP P- rt cj PP P- Ω P tr LQ Pi rt tr Ω P φ P cn φ φ Ω O p- P- i Hi Pi P φ P tr¹ P P- P cn H- tr Hi O: o P. "* 'p rt tr φ φ Dd P LP P tr Ω P Ω o LQ o P rt P- φ P P- P rt PP cn OP 3

• rt P P- φ CΛ LQ P P. P^J r P tr φ o «φ P - - o PPP φ HH p-

pPZP¹ &lt;φ φ PO P rt H- P o P P- P • P ^ f LQ Hi P φ P- P- Q cn P

INI P i φ φ P φ tr PP cn φ p φ P- PP cn φ PP CΛ P- H- "tr PP P- φ rt P.

P LQ o cn LP LP PO: LQ cn P 3 rt CΛ P P- P * Ω CΛ P tr LQ Φ o P cn P

P cn o P φ tr P iQ φ P LP φ P- PP P-tr tr • Ω P^J cn φ • P- cn 3 P P- rt P Φ

Φ cn P i P P rt φ φ PP φ O φ P CΛ φ P tr r Ω P Ω O 3 φ P'-φ φ p tr

3 P- P o LP P- P ^•PM φ LP φ Pi PP rt P o φ φ tr φ CO tr P rt Ω n ¹ φ Φ

P Pn cn P P- xs P Φ O CΛ O o tr P 3 P- PP^J P- N α o tr PP^J P z PP P rt PO Ω φ tr O tr z PPP φ P P Ω Q φ φ Ω cn P rt LQ •

P- P p - P p tr tr: Pi PP li φ φ cn Ω P- iQ Za P φ tr Φ P- PZ tr rt iQ Φ

PP rt cn tr φ LP rt PP rt PPPO tr tr P φ φ rr tx&gt; N rt P φ φ ω Z LQ ö

P Φ o P- P P- Φ Q Φ P P- Φ P. P φ rt NP P- Φ K Φ P- CΛ cn &lt;! d Φ P

PP 0 CΛ P LQ Φ rt rt P cn ZP P- φ Φ P Φ Φ &lt;PP P- LP P Ω P- φ HP

PP φ φ P φ cn cn φ P- Ω PP φ P φ P- P. P ι Q P tr rt Dd H α cn tr

P-LQ O cn P p: P φ P φ tr P-P LQ P tr P rt tr n φ P φ tr φ φ P-

Φ Φ P. t 3 P i LP P P. P Ω rt Φ P cn. Φ PPZ P-p-Φ

P Φ Φ Φ rt P. P i P φ P φ PP φ tr lH o φ P φ φ N z P rt φ P rt P

P-Ω OP CΛ Φ PP

? PPP φ φ PP P- P φ PP P- P öd φ PP P- LQ PZ P-

Ω φ rt P 1 tr OQ Ω PQ CΛ P cn pi NP φ LP P φ OPP P- π P t cn P- φ P rt rt tr cn CΛ tr φ P Dd o P Qr P- φ PPPPPH Φ H

Φ rt φ Ω PPP P- Pi P &lt;i φ XI φ P- 3 φ o T) φ PP φ LP LQ P. Ω

P Φ P- tr N rt £ P P- Φ Ω OP Φ CΛ PP P- P rt P- P i P cn P Hi tr P cn ω tr

P rt P φ P P -φ LQ 1 P tr tr PP CΛ φ P φ 1 cn p. PP cn Φ Φ 1 P P- P-¹

P Φ ω &lt;! H cn rt O tr Φ P rt P 3 XS P- P rt Φ 3 Cd P- φ P d OP

LQ P Φ 1 P. • rt P-PP φ P-PPPP P-P P LQ H 1 φ cn cn φ φ φ P φ 3 φ P φ P-P φ P φ Ω li 1 PPP 1 PP^J 1 PPP 1 1 tr

co CO ro t P&gt; P¹

Cπ o cπ σ Cπ o cπ

<img file="WO02082195A2_D0006.tif" />

To plan a ternative trajectory, all outbound, directed coordination links are removed. As this interrupts the closed loop, it blocks the blockage. The replication is then discarded. However, if a robot receives a reprogramming initiated by itself, it can be concluded that no robot in the circle was able to plan an alternative trajectory.

If a block could not be resolved during the first step, it may be because this is temporarily not possible. This case may occur, for example, when other robots in the vicinity of a robot prevent them from creating a new trajectory. These two cases can be distinguished by the following criterion:

If none of the participating robots are able to plan an alternative trajectory, and if none of the involved robots have an uninvolved robot in its neighborhood, then the obstruction can not be resolved by asking individual robots to plan alternative trajectories.

A robot is considered to be involved if it is part of the circle, or if it is attached to the circle through an outgoing coordination link either directly or transitively. FIG. 4 shows by way of example a blocked circle of the robots 1, 2 and 3, as well as a number of participating robots.

The idea of ​​the second step in the planning of an alternative trajectory is now to test this criterion and to ask involved robots, who are not part of the circle, whether they can plan alternative trajectories. As a result, as many blocked robots as possible can be freed. o co ro ro P¹ P¹

Cπ o cπ o Cπ o cn tr ≥; Hi 3 φ rt tr ^ cn Dd tr rt φ tr CΛ &lt;QP α P Pi P α P ö P Hi P¹ Dd Sl φ PP P- P- φ P- PP P- φ φ 3 PP d P- P- φ PP φ φ P z φ φ PP φ φ p

P- P cn φ PPP cn P o P- SP 3 B Ω φ P φ cn P P- tr BPP φ Z tr o 3 cn P φ α cn P Ω z φ Hi CΛ 3 P tr P P- Ω rt φ Qr Φ P- tr φ P xs φ φ rt 3 Pi d cn tr P P- p: Ω φ cn rt öd CΛ tr α cn P- d Pi P d φ iQ φ

P- tr P • o P tr P- rt LQ P tr P^J tr φ PP d P li φ P rt PB φ P Dd tr P φ r φ φ rt iQ PPP Pl Hi φ P d P φ z ιΑ φ P LQ φ B d ü b-&gt; o P- φ P rt φ rt Hl tr φ HPPP^J Ω P φ P- ω cn P-LQ

ZP P- o p PPPP rt B P- Φ Q P- tr tr PN ω Φ 3 cn Qr

Qr P- P φ Ω φ PP o φ P- P- φ Ω PP d P- φ P-tr φ φ P cn t P LP i pi: LP P tö Qr tr tr PP tr tr tr PP^J φ iQ N rt -^r QP CΛ cn PP¹ Φ P- Φ p- d cn PO P- Φ P.P Φ Φ rt Φ rt P Φ P cn rt tr

O: φ cn Ω ö&gt; B tr φ Hi CΛ &lt;Q φ LQ i-i PP φ tr P φ PN φ P cn Pi P φ P tr φ O: o P- P- φ cn cn Λ P cn φ BP Ξ

PP φ OP P- φ rt P cn P rt φ P Ω X S 3 P d Z t o O φ P- LQ z Φ

Pi tr P tr BP - P cn d P φ PP tr Pi φ φ P oo tr b-&gt; Qr PP PS P- P-

P- PO Φ rt B rt P CΛ H φ PPP^J 1 α tr tr P Ω φ * P φ OP rt

P p φ rt Λ ιp LP cn PBP Φ α d Φ o tr tr PP Φ P- tr P Φ

P P- Φ w W c c d d P- φ • p- rt P- d P P. P- rt Φ Φ cn 3 POB

PPP ι-i φ φ cn P tr P- H Ω cn P iQ P- φ P Pi cn φ rt

P Qr Φ φ z P PZZ Φ φ tr S! tr Z φ LQ φ PP Pi o φ φ P φ o CΛ

LP φ cn P P- φ α PP φ P CΛ φ rt φ cn N p- O o P cn cn PP Ω

CΛ P Φ tn LP φ P tr PS rt PP z φ CΛ φ ro Z tr P φ N tr

LP Dd p- "d PPPP Φ P tr P cn P- P- Ω Φ o P- d P. P- Q d P

Φ ^ d ^ 3 tr P Φ cn P P- Φ φ P- P LQ tr LQ P- LP rt p- P Φ rr Φ iQ P-

3 P- O φ φ LP tr P- Ω PPPP φ rt PP Qr φ Z φ P φ BP cn n cn rt p: LP Ω P rt cn PP tr P- LP P P- P- φ α PP cn P- LQ P P Ω Z rt

ZP PX φ tr P φ φ φ φ P rt P P tr tr • P rt rt φ φ p. Dd d tr φ CΛ

Φ P P- Qr P- PPP p- cn Q P- P^J O: Φ NP P- -i P- Φ P- P-

P φ φ P tr B Dd rt P- Pi P- PPP p- P- P P- d φ Hl Ω cn N

PPP P-P LP Φ Φ Φ φ o iQ PP dd Ω φ cn p-PPP tr φ P

&lt;! d P LP P φ P- P b-&gt; 3 P tr rt φ N r P tr P cn φ LQ σ φ φ rt P φ Cπ P rr p: PP Ω P- b-&gt; S rt o φ B d N rt Φ rt Φ cn Φ P- P • φ '

P LP P Φ PP P-p rt p rt h rt Φ Φ P P rt P P-xs

Pi tr cn PPP o φ LP φ P tr φ Pi d P _^«P rt P P- Φ Φ P Pi ö PP^J

P P -X φ tr PPPP o PP φ φP P- iQ li P- φ P tr cn i-i tT Pi PP rt «3 P Pi LQ rt tr LQ d φ P ω M tr b- cn φ φ B

P φ φ OP cn φ P iP ι-i φ φ o φ 3 LQ φ P Dd P- P- 3 P cn Dd P

Φ KΩ P- P- tr cn rt φ P- P P- rt p P rt XS Hi Φ B LQ Φ cn Φ B

P ^•»Cn P o X Φ P rt s: P φ 3" • tr Φ Hi P ^ 1 Hi Qr rt P "φ Hi Q

CΛ Φ Φ rt PXP Φ tr Φ φ P Φ P Φ Φ P- P d Φ P- LQ PP

Φ cn 3 φ P φ φ tr PP P-PT o P- P- P- ιQ φ BPP φ Pi φ Φ

&lt;! P- PP P- Pi P- P- tr E d PP tr • t P P- LQ B cn 0 P- P- φ P 3 &lt;P o P φ p φ φ o Hi Hi φ P d φ Pi LP Ω d B

P φ φ tr φ o rt P 3 P φ HI Ω o P φ φ LP J ^&gt; PB o tr LQ P φ

P tr P P - PPPP Hl • PP tr PP^J P P- P- ω LQ tr φ P- rt LQ P

PPP Hi φ φ φ P d φ 3 rt φ 3 P-tn N o P Ω cn

CΛ cn PPPP P- rt PB ö P- P- P Φ Pi φ B Φ cn 3 d rt 3 PX 3 P

Ω Hi rt tr p: P φ P φ P φ α PP rt P o rt φ φ O: rt P- φ P^J tr p: Φ P tr Φ P P- P φ PPP P- P tr P sl P^J PP LP P rt

P tr P- Φ Φ B φ P tr CΛ Q p. o P o φ φ d P-tr Z Qr P φ d PP^&gt; PH tr P cn Hi Φ Pi ω cn Φ P rt rt P LQ P Φ P Φ d P- P- Φ PP

P ^ P • P φ POP φ O 3 K φ H- φ LPBPP Ω H 3 PP

P- PN P- H rt P b-&gt; P^J B tr P Φ P &lt;JP Sl p LQ Λ rt tr P iQ P

Ω LP d P φ LP P-¹ P¹ P o b-^&gt; ≥; Φ P φ 3 &lt;! Sl d Φ rt P. rt tr cn 3 Hi Φ p cn rt rt Φ rt PPN^•* LQ φ φ tr Φ 1 P- P P rt 1 o P^J &lt;Φ rt φ φ d Ω d U⁾ Qr HQ Φ PZP Φ P

• Cd PP P- Φ PP tr φ P. 1 Φ &lt;P- B Φ

P 1 P ∈ PP tr ^ Q 1 Pz φ 1 p: PB φ PP Dd PP 1 1 1 P- φ φ φ tr PP φ ^&gt; φ 1 1 1 1 1 1

For this purpose, the inventive method was implemented with the algorithms preferably used and tested in the simulation. As a test model, two different environments have been adopted, namely a supermarket with only one room and a series of shelves, as well as an office-like environment, which consists of a plurality of interconnected by a corridor rooms with individual obstacles. This is shown in Fig. 5, wherein Fig. 5 a) the supermarket and Fig. 5 b) shows the office. The surroundings had a size of 10 x 15 m.

The robots used for the simulation had a size of 1 m and a width of 0.8 m and were moved at a speed of 0.3 m / s. In FIG. 5, 5 robots each are shown in the different environments.

For each environment, 6 simulation runs were carried out with 1 to 6 robots each. Each of the 12 simulation runs ran for 10 min. During the simulations, the robots followed suitably planned trajectories. For the evaluation of the simulation runs, the average number of coordination connections for a robot, the number of resulting blockages and the average trajectory length of the robots were determined after each simulation run.

FIG. 6 shows the average number of coordination connections of a robot, FIG. 6 a) showing the result for the supermarket, and FIG. 6 b) showing the result for the office. As can be seen from Fig. 6, the rises^' average number of coordination links almost linear with the number of robots. The reason for this is that the average number of coordination connections depends on the number of robots in the vicinity of a robot, which depends linearly on the number of robots used.

In Fig. 7, the number of mutual blockages of the robot is shown. Again, Fig. 7 a) shows this for the o co t ro P¹ P¹ cπ o Cπ o tn σ Cπ cn! d PP &lt;Dd 3 P- P ^ cn rt CΛ Pi MQ tr Z ^ 1 cn tu P PP tr N Q. CΛ ^

Φ φ PP P- φ d φ φ PP o P P- φ d OP φ o φ P Ω P- o O φ P P- z φ P- P rt Hl P φ 3 CΛ PZ CΛ Ω P¹ 3 P tr PB LP cn tr PPPBP cn φ rt Φ

PNP p: z φ cn L tr P φ O ^ P- PP rt φ rt cn P- P-

P rt O: P φ tP Qr φ LP φ φ 3 P rt P- Ω rt P P- φ P. Qr P Qr ZPQ φ cn PP φ p- PPP LQ &lt;QP&gt; P P- 3 φ LP tr φ LP PPP iP Φ P- -&gt; PP φ P-

BP Pi φ PP • φ φ 00 rt rt PP • rt P cn rt φ P φ φ BH 3 φ QP LP &lt;cn φ PP o P- P φ tr P- PP α P- P. cn φ PS LQ φ z φ φ rt cn Sl CΛ P- o φ ir 00 rt P. P φ Ω φ p: Pi φ P 3 φ rr QO o PP tr P- φ PSP P- rt P φ d tr Hi rt o P- cn P P. P Λ

Φ tr &lt;! O: tr Hi Ξ P φ P-Q φ P cn P P- PPP Dd tr Hi tr B cn P^J P • cn d tr o O cn φ P CΛ φ tr rt φ rt Hi φ LP CΛ Ω φ φ φ P o ISI φ P- S

Φ rt P rt P- tr P- HBP P- P Φ PP d Φ rt «tr PO P- B rt φ Qr Q P- Sl ιp φ

P Φ P 3 PP¹ PPHB cn O Ω rt φ "PP P- P li

Φ P Dd Z i Φ P Φ P: CΛ Φ cn P rt cn O Φ P tr Φ n B cn O: Pi φ P- 3

PP^J Φ o P b-&gt; PP P. Z P&gt; Φ φ Ω P P- d P- p- ZPP φ tP o Hi P cn OP b-^&gt; P • LP ^ Dd P Φ o cn&gt; xι tr. P Hi φ P φ Qr B Dd φ tr P P- P

CD P- Ω P P rt Φ P- P- Ω P- P^J "P- Φ PP P- H- P p: li o P iX tr

P ιQ X φ P- P P- LP o rt 3 tr πPt P- P φ PPP φ LSI -i rt cn P rt θ: B P- P cn O cn Ω P- P- Z • • φ P - tr P Φ LP LP P o P Φ P cn

&amp;&gt; p- Φ P- P P- tr φ tr P P- 7- φ O: LP P P. cn φ 3 P^J P ^ rt

Φ Hi P o Φ LP co P- Φ P CO ^ H o cn φ PP^J 3 φ cn P P-d

P- P α PPZP Φ Pi z P- P- d rt P Φ P 3 3 φ P- LP NB

3? P P φ p- P φ PO φ p: P- tr ιp Ω P φ P- d P- pj: PP P- P

Φ PP Φ P ir &lt;P Hi PP tr LQ P LQ - ^• • tr QZ 3 PP rt φ 3 P- tr B φ P P- Pn c P o φ Hl X ng φ PN Ω P- &lt;5 φ -J ^

P rt P ^ LP tT P- LQ rt P rt Φ P 00 &lt;! 3 ι-i cn φ tr N iQ φ 3 CΛ Z P- o φ φ φ P Ω φ φ «P- φ P- φ x Qr cn P¹ d H tr dg φ Φ ^ x

PNP rt PPP tr PP rt PP φ P φ rt PPP tr tr φ s φ PP.

P P- z 3 P- cn rt α X 'tr tr P φ φ P φ φ P- P- φ P cn P

CΛ 3 φ P- cn P- LQ P P- P &lt;1 φ 3 P- li&gt; • PP Ω t BP o P LP P-

P φ rt Ω P P φ P φ PO P tr P- P d tr d P- φ 3 φ Ω 3

&lt;Sl rt PP tr tr Ω P Hi PPP φ rt P- PP rsi φ rt φ P tr φ 'tr

P- Φ P- φ rt tr P φ rt φ CΛ rt d LQ dd P- P- BNB CΛ PP rt tr φ P 3 LP PP^J rt P- P cn o CΛ Ω PPP 3 P rt p rt tr PP

PP P- tr -&gt; P- P- s: P- Φ P rt P- tr Φ Q Ω 3 Φ φ • Φ Φ rt P- Hi rt Φ Φ Ω φ CΛ PP cn Ω co Dd PP Φ O tr Φ PBP^J • Pi Ω PP

Pi tr P- Dd tr P rt P: tr p: φ φ P cn P Dd o o tr P o φ P rt Pi P _^»P. Ω 3 P P- do \ o Φ P Φ rsi Φ Pi Φ t cn tr P- Φ OOP φ tr Φ \ o tr Dd Hi Pi P- ιp PP o 3 φ P" P- P. o PN Ω tr α 3 Hi P-PP¹ P- cn cn rt Φ LQ P- Qr PP φ tr PP P cn &lt;! φ rt PP tT OP φ p: φ p- P • Z φ Ω φ φ P LP Cd PP cn rt P- P

Φ φ P P rt cn tr b ^ z Ω tr z φ P^J tr P cn P P- P- PO P-&gt; Φ

PP Φ Φ cn PPP tr Pi Φ σ P- iQ O: rt rt d PP P. Hi POP ^

N Cd PP rt d P φ o ZP φ P n P Dd φ φ PP Hi ozd P P- P φ tr PH d PP Hi rt P tr φ P. B rt B d P- LP P φ P φ cn Pi

P- φ tr Hi PNP * P LQ φ o iP cn φ Q iQ o S LP cn *⁾ d P- B rt o P^J

P rt b-¹ PP d cn cn P- Φ P si rt rt P- P CΛ Z cn Ω P^J rt Z o cn cn tr QP cn φ φ φ Φ * • Ω tr φ cn P. P tr cn σ rt tr P- P o

Φ P cn P t φ &lt;O: 3 PP tr P. PP P- P- P tr o P- P- 3 3 rt φ ω Ω φ P o P p- 3 cn P rt d φ tr P φ d P rt P. φ φ φ cn φ tr PP φ o Hl φ P- rt cn φ P- P φ PP φ PPP 1 φ φ cn PP Dd • ^ P rt rt LP PP p- P rt cn 3 P- P cn P LP P cn Φ p: Hl PP Odd

N Φ Φ Hi PB rt Z φ cn P ^ p: • PPP 3 p: P b-- &lt;P rt rt P- d P P- Qr S b-¹ Φ B P-tr Φ PB Φ LP Pi PO Φ P

Φ PP cn 1 PO Φ HB Φ P- Pi P¹ LQ P-φ Φ P-OZ P-Φ H o

For example, LP P.CΛP tri-i P.d P cn BO φ BPHB 1 P-Ω NZ cn

Φ φ rt LP o φ φ B rt φ tr φ cn HP tr P- Z φ • li 1 cn rt P P- φ O α P öd P- P- φ φ OP 1 ff 1 φ φ P 1 φ φ φ 1 LQ P-P 1

1 P 1 CΛ P 1 rt 1

den, the performance of the process decreases significantly, as can be seen from the average path lengths.

In summary, therefore, it should be noted that with the method according to the invention a decentralized coordination of the independent trajectories of a plurality of mobile robots to avoid collisions, and detection and release of blocking circuits takes place.

This is essentially done by a combination of three algorithms that reliably solve the task. These do not use global synchronization, do not interact with each other and only require local communication between the robots. Global coordination of a set of robots is achieved by allowing more than one coordination link for each robot. This networks a set of robots into a global structure.

Mutual blocks in global coordination that can not be avoided if only local coordination is used are reliably detected. The mutual blockages are solved by reversing the direction of coordination links and asking robots to change their trajectories. The only mutual blockages that can not be resolved are those in which the trajectory planning units of the affected robots are unable to create alternative trajectories. However, this depends only on the capabilities of the robotic unit planning the trajectory and the characteristics of the environment.

The strict separation between the planning of trajectories on the one hand and the collision avoidance / handling of mutual blockings on the other hand makes it possible to use completely different working units planning the trajectories. The only limitation is that they must be able to plan alternative trajectories.

Of course, the invention is not limited to the movement of mobile robots. Mobile robots within the meaning of the invention may also be mobile parts of robots, for example robot gripping arms.

An advantageous application of the method according to the invention is the coordination of the independent trajectories of a set of mobile robots for the common cleaning of a large room, e.g. As a large supermarket, a warehouse or an airport.