Decentralizirano planiranje misija za heterogene robotske timove temeljeno na hijerarhijskom prikazu zadataka

This thesis focuses on the planning and coordination of cooperative missions for heterogeneous MRS. This complex problem consists of mission decomposition selection (the question what do we do?), task allocation (the question who does what?), and task scheduling (the question how do we arrange tasks in time?), which are often summarized under the common term mission (task) planning. Mission planning can be viewed as an optimization problem that attempts to find the most appropriate way to execute a mission, given certain criteria. Overlaid on this process is a set of coordination mechanisms that ensure timely and coordinated planning and execution of tasks between multiple individual robots. This thesis proposes a distributed, multi-stage optimization method for planning complex missions for heterogeneous multi-robot teams. This class of problems includes tasks that can be executed in different ways and are associated with cross-schedule dependencies that constrain the schedules of the different robots in the system. In nature, these are NP-hard problems, and obtaining exact solutions is computationally intractable. The approach proposed in this thesis involves a multi-objective heuristic search of the mission model, represented as a hierarchical tree that defines the mission goal. This process identifies multiple favorable ways to accomplish the mission (task decomposition selection), which feed directly into the next phase of the method - task allocation and scheduling. For task allocation and scheduling, a distributed algorithm is proposed for missions where the tasks of different robots are tightly coupled with temporal and precedence constraints. The approach is based on representing the problem as a variant of the Vehicle Routing Problem (VRP). The solution is found using a distributed metaheuristic algorithm based on evolutionary computation (CBM-pop). Such an approach allows for fast and near-optimal allocation and can therefore be used for online rescheduling in case of task changes. Simulation results show that the approach has better computational speed and scalability without loss of optimality compared to state-of-the-art distributed methods. Finally, this work defines a decentralized coordination framework for heterogeneous multi-robot systems (GEM). The framework includes coordination mechanisms that ensure coordinated mission planning and execution. It also implements a complete software infrastructure that interacts with the specified hierarchical task model. It is domain-independent and supports different missions for heterogeneous multi-robot systems, as long as they conform to the mission specification model. The proposed solutions are thoroughly tested in a realistic simulation environment as well as in real experiments using heterogeneous multi-robot systems. The proposed algorithms are directly compared with similar methods in the literature and the results show that our method can handle more complex missions with good scaling properties. We provide suboptimal solutions in fast computation times, which makes the proposed solutions particularly suitable for real-world robotics applications. The following original scientific contributions are achieved in this thesis: a) A framework for decentralized task allocation, scheduling, and coordination of heterogeneous robotic teams based on hierarchical task representation. b) A method for distributed task allocation and scheduling for heterogeneous robotic team missions with cross-schedule task dependencies. c) A method for distributed mission decomposition selection for heterogeneous robotic team missions with complex task dependenciesFokus ovog rada je planiranje i koordinacija kooperativnih misija za heterogene višerobotske sustave. Ovaj složeni problem sastoji se od odabira dekompozicije misije (engl. task decomposition selection; odgovara na pitanje koji zadaci se trebaju obaviti?), dodjele zadataka (engl. task allocation; odgovara na pitanje tko radi što?) te vremenskog raspoređivanja zadataka (engl. task scheduling; odgovara na pitanje kako vremenski rasporediti zadatke?), koji se često sažimaju pod zajedničkim pojmom planiranje misije (zadatka) (engl. mission (task) planning). Planiranje misije može se promatrati kao problem optimizacije s ciljem pronalaska najprikladnijeg načina izvršenja misije prema zadanim kriterijima. Skup koordinacijskih mehanizama nadgleda ovaj proces te osigurava pravovremeno i koordinirano planiranje i izvršavanje zadataka više pojedinačnih robota. Ovaj rad predlaže distribuiranu, metodu optimizacije za planiranje složenih misija heterogenih višerobotskih timova. Ova klasa problema uključuje zadatke koji se mogu izvoditi na različite načine i povezani su s međuovisnostima koja ograničavaju rasporede različitih robota u sustavu. U prirodi su to NP-teški problemi, a dobivanje točnih rješenja računski je nerješivo. Pristup predložen u ovom radu uključuje heurističko pretraživanje modela misije, predstavljenog kao hijerarhijsko stablo koje definira cilj misije. Ovaj proces identificira višestruke povoljne načine za postizanje misije (odabir dekompozicije zadatka), koji se izravno uvode u sljedeću fazu metode - dodjelu zadataka i raspoređivanje. Za dodjelu i raspoređivanje zadataka i predložen je distribuirani algoritam za misije u kojima su zadaci različitih robota usko povezani s vremenskim i prioritetnim ograničenjima. Pristup se temelji na predstavljanju problema kao varijante problema usmjeravanja vozila (engl. Vehicle Routing Problem, VRP). Rješenje je pronađeno korištenjem distribuiranog metaheurističkog algoritma temeljenog na evolucijskom proračunu (CBM-pop). Takav pristup omogućuje brzu i gotovo optimalnu alokaciju te se stoga može koristiti za online replaniranje u slučaju promjene zadataka. Rezultati simulacije pokazuju da pristup ima bolju računsku brzinu i skalabilnost bez gubitka optimalnosti u odnosu na najsuvremenije distribuirane metode. Predložena rješenja temeljito su ispitana u realističnom simulacijskom okruženju, kao i u stvarnim eksperimentima korištenjem heterogenih višerobotskih sustava. Predloženi algoritmi izravno se uspoređuju sa sličnim metodama u literaturi, a rezultati pokazuju da predložena metoda može isplanirati složenije misije, bez velikog povećanja vremena izračuna rješenja. Pružena rješenja su suboptimalna, ali dobivena u brzom vremenu računanja, što predloženu metodu čini posebno prikladnom za primjene u robotici. Disertacijom je ostvaren sljedeći izvorni znanstveni doprinos: a) Radni okvir za decentraliziranu dodjelu i vremensko raspoređivanje zadataka, te koordinaciju heterogenih robotskih timova temeljen na hijerarhijskom prikazu zadataka. b) Metoda za distribuiranu dodjelu i vremensko raspoređivanje zadataka heterogenih robotskih timova za misije s međuovisnostima zadataka različitih rasporeda. c) Metoda za distribuiran odabir dekompozicije misije heterogenih robotskih timova za misije sa složenim međuovisnostima zadatka