Evolutivni algoritam za upravljanje višeagentskim robotskim sustavom

doctoral thesis

• Title (english): An evolutionary algorithm for controlling a multiagent robotic system
• Author: Petar Ćurković
• Mentor: Bojan Jerbić (mentor)
• Committee member: Josip Kasać (predsjednik povjerenstva)
• Committee member: Bojan Jerbić (član povjerenstva)
• Committee member: Danica Kragić (član povjerenstva); strani drzavljanin: Nije dostupno
• Granter: University of Zagreb; Faculty of Mechanical Engineering and Naval Architecture; Zagreb
• Defense date and country: 2010-11-19, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Basic Technical Sciences; Automatics
• Universal decimal classification (UDC): 004 - Computer science and technology. Computing. Data processing ; 621 - Mechanical engineering. Nuclear technology. Machinery

Abstract

U ovoj disertaciji razvijena je metodologija za planiranje kretanja dva robota 2R konfiguracije koji dijele radni prostor i predstavljaju dinamičku prepreku jedan drugome. Ovaj problem spada u klasu NP kompletnih problema, čije je rješavanje egzaktnim matematičkim algoritmima s poznatim gornjim granicama vremenske složenosti ograničeno primjenjivo. Razvijena metodologija planiranja kretanja temeljena je na istodobnom rješavanju problema planiranja kretanja za dva robota paralelnim, dijelom neovisnim evolucijskim - koevolucijskim algoritmom. Postavljena je i potvrđena hipoteza o mogućnosti vremenski efikasnog planiranja kretanja za dva robota temeljena na predloženom koevolucijskom algoritmu. S ciljem potvrđivanja hipoteze, razvijeno je simulacijsko okružje u kojemu je, za različite početne i konačne konfiguracije, moguće planirati kretanje za jednog, ili više robotskih agenata u radnom prostoru koji može uključivati stacionarne prepreke. Određen je skup kriterija kojima je moguće vrednovati ponašanje agenata, te su utvrđene prirode veza među pojedinim kriterijima. Skup kriterija čine kriteriji broja sudara, ukupno prijeđenog puta, kuta zakreta u zglobovima te neravnomjernosti profila brzine. Izvršena je formalna analiza sustava sastavljenog od dva robota 2R konfiguracije te su izvedeni analitički uvjeti za postojanje sudara među robotima. Izvedeni su izrazi za izračun potrebne duljine gena evolucijskog algoritma. \Na temelju ovih spoznaja formulirana je funkcija dobrote i odgovarajuća metoda izbora agenata, čime je omogućena njihova paralelna evolucija i međusobna prilagodba, koja rezultira neprekinutim, vremenski i energetski učinkovitim gibanjem bez sudara od početne do konačne konfiguracije u radnom prostoru. Sa svrhom dodatne uštede procesorskog vremena, predložena je metoda diskretizacije kretanja robota te komplementarna metoda rekonstrukcije kretanja s proizvoljno malim vremenskim intervalom između dvije uzastopne robotske konfiguracije. Metodologija je verificirana na realnom robotskom sustavu, sastavljenom od dva robota za koja je problem planiranja kretanja razvijenom metodologijom uspješno riješen.

Abstract (english)

In this thesis a method is developed to solve the problem of path planning for two 2R type
robots, which share workspace and thus present dynamic obstacle to each other. This
problem, according to its computational complexity, belongs to NP complete class problems.
Solving such problems with exact mathematical algorithms with known upper time
complexity bound is limitedly applicable.
The motion planning methodology developed in this thesis is based on concurrent path
planning of both robots using parallel, partly independent evolutionary – coevolutionary
algorithms. Time efficient planning is possible for two robots using developed algorithms
what proves the hypothesis formulated in the dissertation.
To prove the hypothesis, a simulation environment is developed in the first step, in
which path planning is possible for arbitrary setup of initial and final configurations of the
robots. It is possible to conduct path planning either for one robotic agent or for more,
including presence of arbitrarily distributed obstacles. Set of criteria is determined to evaluate
the evolution of agents, and the nature of connections between different conflicting criteria is
revealed. Number of collisions, total path, joint rotation angle and velocity profile of the end
effector are the criteria to be optimized. Formal analysis of the system composed of two 2R
type robots is conducted and analytical conditions for collision occurrence are derived.
Based on these understandings, the fitness function is formulated with appropriate
selection mechanisms, what enabled parallel evolution and adaptation between the two
robotic agents. The result is continuous, time and energy efficient motion without collisions
for the two agents in the given workspace.
To additionally optimize processing time; a motion discretization method is proposed
together with complementary motion reconstruction method to execute the motion with
arbitrarily small time step between two consecutive configurations.
The methodology proposed in this thesis is verified on a real robotic system composed
of two robots for which the path planning problem is successfully solved.

• Keywords: evolucijski algoritam; planiranje kretanja; robotika
• Keywords (english): evolutionary algorithm; motion planning; robotics
• Language: croatian
• URN:NBN: urn:nbn:hr:235:892168
• Study programme: Title: Mechanical Engineering and Naval Architecture; Study programme type: university; Study level: postgraduate; Academic / professional title: doktor/doktorica znanosti, područje tehničkih znanosti (doktor/doktorica znanosti, područje tehničkih znanosti)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2020-06-26 12:53:41