Plánování pohybu skupiny robotů pomocí flocking algoritmu a Voroného diagramů

Using Flocking Algorithms and Voronoi Diagram for Motion Planning of a Swarm of Robots

conference paper

Czech

Článek prezentuje techniky pro řízení a plánování pohybu skupiny robotů mezi dvěma danými místy v prostředí s překážkami. Tyto techniky jsou založeny na „flocking“ algoritmu simulující přirozený život, ve kterém mohou být simulovány houfující se či rojící se zvířata jako např. roje včel nebo hejna ryb, ale s menším ohledem na realitu jejich pohybu. Pro nalezení nejkratší cesty je použit A* algoritmus ve spojení s Voroného diagramem, který je jednou ze základních datových struktur ve výpočetní geometrii. Nejkratší cesta tvoří základ pro vytvoření koridoru umožňující přesun skupiny robotů. Jednoduchá pravidla pro simulaci shromažďujícího chování roje – řídícího chování – jsou separace, koheze a zarovnání. Hlavním cílem skupiny robotů je dosáhnutí co nejrychleji cíle při udržování koheze skupiny a zajištění toho, že skupina má největší možnou vzdálenost od okolních překážek. Používáme kombinaci řídících chování k zajištění bezkolizního pohybu skupiny robotů uvnitř koridoru, která je postaven podél nejkratší cesty. Roboti nacházející se v přední části skupiny vedou skupinu a počítají nejkratší cestu zatímco zbytek skupiny je následuje (Reynolds, 1999).

This paper presents some techniques for controlling and motion planning of a swarm of robots in an environment with obstacles between two given places. These techniques are based on the flocking algorithm presented by (Reynolds, 1987) for simulating natural life in which we try to simulate real life herding or swarming animals like swarms of bees or schools of fish, but with lesser consideration to the reality of the motion. To find the shortest path between two places we use the A* algorithm and the Voronoi diagram, that is the data structure in the computational geometry. The shortest path serves as a basis to create a corridor to transfer a swarm of robots. Simple rules for simulating the flocking behaviour of swarm – steering behaviours – are separation, cohesion, and alignment. The main goal of the swarm of robots is to reach a destination as fast as possible, while strictly maintaining the cohesion of the swarm and to assure that the swarm has the biggest distance from obstacles as possible. We use a combination of steering behaviours to produce a collision–free motion of the swarm of robots within a corridor that is built along the shortest path. Robots at front of the swarm lead the swarm, which means that they run path finding algorithm, while the rest of swarm follow the leaders (Reynolds, 1999).

plánování cesty, následování cesty, shromažďování, skupinové chování, A* algoritmus, Voroného diagram

Path planning, path following, flocking, group behaviour, A* algorithm, Voronoi diagram

ŠVEC, P.

2005

1. 4. 2005

VŠB-TU Ostrava

Ostrava

80-248-0774-2

Proceedings of the XXXth ASR ‘2005 Seminar Instruments and Control

449

455

7