| Abstract | Područje istraživanja doktorske disertacije su centralizirane metode za koordinaciju u sustavima s više vozila kojima se sprečavaju zaglavljenja te kolizije između vozila i objekta u prostoru, uz ostvarivanje što veće protočnosti. Metode prikazane u disertaciji temeljene su na diskretizaciji okruženja na resurse, pri čemu kapacitet resursa označava broj vozila koja se istovremeno mogu na njemu nalaziti. Na ovaj način definiran je sustav za pridjeljivanje resursa te je koordinacija temeljena na metodama inspiriranima upravljanjem proizvodnim sustavima. U disertaciji je istraživano nekoliko vrsta sustava s više vozila. Za sustave bez ograničenja na tijek izvođenja zadataka predloženo je upravljanje koje se temelji na primjeni Petrijevih mreža i proširuje postojeće metode te rezultira manjim skupom složenih kružnih čekanja koja treba nadzirati, čime se postiže bolja protočnost sustava. Nadalje, u disertaciji je opisana modifikacija Johnsonovog algoritma za određivanje jednostavnih kružnih čekanja kojom se skraćuje vrijeme izvođenja algoritma. Također, u disertaciji je prikazan algoritam za pridjeljivanje staza kojim se značajno pojednostavljuje struktura sustava te broj kružnih čekanja pri čemu se duljina putanje u odnosu na najkraću putanju značajno ne povećava. Osim sustava bez zadanih ograničenja na način izvođenja zadataka, proučavaju se i dvije kategorije sustava s ograničenjima. Prvu kategoriju čine sustavi kod kojih je zadan redoslijed prolaska vozila nekom točkom okruženja. Za takve sustave predložen je algoritam koordinacije vozila koji se temelji na Bankarevom algoritmu. Drugu kategoriju čine sustavi u kojima vozila imaju kružne staze koje se uzastopce ponavljaju. Za takve sustave primijenjeno je upravljanje kod kojeg se plan dodjele prioriteta vozilima zadaje unaprijed. Za takvo upravljanje u disertaciji je definiran postupak određivanja perioda sustava primjenom matričnog modela i maks-plus modela. Valjanost metoda i algoritama pokazana je matematički, a verifikacija i analiza učinkovitosti provedene su simulacijski te eksperimentalno primjenom Pioneer 3DX mobilnih robota te makete željeznice. |
| Abstract (english) | This dissertation presents methods for centralized coordination of a system of autonomous vehicles that perform tasks in a given environment. An example of such a system is an automated warehouse where autonomous vehicles are used for transferring goods, intelligent transport systems where autonomous vehicles are used for transportation of passengers, systems of autonomous vehicles for surveillance, etc. The objective of coordination methods is to control the execution of vehicles tasks to prevent deadlocks and collisions among vehicles, obstacles in the environment and people, and to achieve the highest possible throughput, that is, the faster execution of tasks. Since the tasks of vehicles change during operation of the system, the algorithms used for coordination should to be of lower algorithmic complexity so that they are applicable to work on a real system in real time. The research presented in this dissertation is based on the discretization of the environment into parts so that each part represents a resource of limited capacity. Resource capacity indicates the maximal number of vehicles that can simultaneously reside in the part of space that corresponds to the resource. Vehicles that move in space pass sequentially through the resources and the control algorithm can allow or deny the vehicle occupancy of the next resource. With such an abstraction of the system, the control methods introduced in the dissertation are inspired by the area of manufacturing systems control. The results show that the application of the proposed methods ensures a stable behavior of the system in real time and that the performance of the system varies depending on the control system. The methods and algorithms presented in this dissertation can be applied to other systems, as long as they can be modeled as a resource-allocation system. In Chapter 1 an introduction into the field of structurally-variable multivehicle systems and typical examples of such systems are given. Furthermore, hierarchical levels of the corresponding control methods and basic examples of the existing control methods for each control level are given. In Chapter 2 a discretization of the environment on resources is defined. Two types of environment discretizations are identified: graph-based and free-range discretization. In order to mo del a multi-vehicle system as a resource allocation system, segmentation of the vehicles path is introduced. At the end of the chapter a formal definition of structurally-variable resource allocation system is given. In Chapter 3 a partitioning of the system state-space on deadlock, safe and unsafe states is given. Co ordination is defined as controlled changes in system states in order to avoid deadlock states. Further, algorithmic complexity of the underlying co ordination methods is discussed and it is emphasized that a trade-off between computational complexity and system permissiveness is necessary when controlling structurally-variable resource-allocation systems. Chapter 4 gives an overview of the current state of the research in the area of resource allocation systems and positions the dissertation research goal in line with the state of the art. In Chapter 5 mathematical tools that are used for modeling of the resource allocation system in this dissertation, Petri nets, matrix models and max-plus algebra are described. In Chapter 6 a description of testbeds that are used for validation of methods is given. One testbed is an automatized warehouse, whose simulation built using USARSim simulator, together with the Robot Operating System for low-level vehicle and workcell control. For experimental validation of the same automated warehouse system Pioneer mobile robots are used. The second testbed, used for validation of cyclic systems control, is a lab oratory mo del of a railway system. In Chapter 7 systems with no restrictions on task execution are studied, that is, systems where the only criterion for vehicle co ordination is deadlock and collision avoidance. For such systems a control method based on the application of ordinary Petri nets is given. The proposed control method builds up on an existing method, which identifies the interaction between circular waits of resources. The proposed method results in a smaller set of complex circular waits that need to be monitored, and therefore results in higher throughput rate. Chapter 8 deals with the analysis of the system, which primarily consists of the determination of a variable set of simple circular waits and the interactions between individual circular waits. In Chapter 8 the basic Johnson’s algorithm for determination of circular paths in a directed graph is modified to avoid unnecessary computations for each change in system’s structure. The result is a dynamic algorithm for determination of simple circular waits, which reduces the execution time when compared to the basic algorithm. In Chapter 9 an algorithm for path assignment is described that reduces the number of simple circular waits of the resource allocation system. Namely, the number of circular waits and the number of interactions between them, that is, the complexity of the system depends on the paths of vehicles. The more the vehicles share paths, the complexity of the system and of the coordination algorithms, increases. Using the proposed algorithm significant simplification in the structure of the resource allocation system can be achieved, and at the same time the length of the path is not significantly increased when compared to the shortest path. Chapter 10 studies multi-vehicle systems where the sequence of vehicles passing through a specific point in the environment is given. For such a system algorithm for coordination of vehicles based on the banker’s algorithm and the modified banker’s algorithm has been described. Chapter 11 studies multi-vehicle systems where vehicles have circular paths that are sequentially repeated. For such a system a specific control method is applied, where the vehicle priority assignments are given in advance. The consequence is that the system always achieves a steady and periodic state. In this dissertation a procedure for determination of the steady-state cycle time of the system depending on the predefined priority scheme, using matrix model and max-plus model, is given. The proposed method can be an initial step in the procedure of system cycle time optimization. Chapter 12 gives the concluding remarks and sets the directions for future work. |
