Ph.D Thesis

Ph.D StudentAltshuler Yaniv
SubjectMulti Agents Robotics in Dynamic Environments
DepartmentDepartment of Computer Science
Supervisors PROF. Alfred Bruckstein
DR. Israel Wagner
Full Thesis textFull thesis text - English Version


In this work we examine the use of a decentralized group of extremely simple robotic agents for cooperatively accomplishing missions of global properties. We show that using only local interactions, such robots can cope with the lack of a central supervisor, communication resources and large memory resources. Using redundancy, the systems also achieve fault tolerance (required as the robots' simplicity might sometimes imply low hardware reliability). We examine problems in which the agents must work in dynamic environments - where changes may take place, that are independent and certainly not caused by the agents' activity. The main problem that is discussed in this work is the Cooperative Cleaners problem - a problem assuming a regular grid of connected rooms (pixels), part of which are "dirty", the "`dirty" pixels forming a connected region. On this dirty grid region several agents move, each having the ability to "clean" the place (the "room", "tile" or "pixel") it is located in. A cleaning protocol for a decentralized group of robotic agents is presented, aiming for cooperatively cleaning a given (yet unknown) dirty region. The protocol's performance, in terms of cleaning time is analyzed and later on also demonstrated experimentally. Later on, the dynamic generalization of this problem is discussed, in which a deterministic evolution of the environment in assumed, simulating a spreading contamination or fire. Once again, the goal of the agents is to clean the spreading contamination in as little time as possible. After formally defining the problem, analytic lower bounds for the problem (namely, for the cleaning time of any cleaning protocol) are presented, followed by an impossibility result. We suggest that the same cleaning protocol which was presented for the static variant of the problem can be used for the dynamic generalization as well. A variety of experimental results are presented, and compared to the analytic lower bounds. The protocol's performance in the dynamic environment is then analyzed, resulting in several upper bounds over its cleaning time. In addition, we discuss the Cooperative Hunters problem, in which a group of unmanned air vehicles should scan a pre-defined rectangular area for a group (of unknown size) of evading targets, of superior sensors and communication resources. This problem, dating back to World War II, is analyzed, and a scanning algorithm for it is presented. This algorithm is then shown to be very close to the theoretical optimal algorithm.