Preview only show first 10 pages with watermark. For full document please download

Formation Of Networked Mobile Robots

Rating
Date

November 2018
Size

4.5MB
Views

5,015
Categories

Baby & children Toys & accessories Toy parts

Transcript

FORMATION OF NETWORKED MOBILE ROBOTS By Samitha W. Ekanayake Submitted in fulﬁllment of the requirements for the degree of DOCTOR OF PHILOSOPHY DEAKIN UNIVERSITY AUSTRALIA c Copyright by Samitha W. Ekanayake, 2009 Formation of Networked Mobile Robots by Samitha Wathsala Ekanayake This thesis presents a novel approach for controlling a robotic swarm to generate a geometric pattern described by a given contour, and a suitable communication scheme which enables the robots to communicate with each other as an all-to-all network. One of many challenges in swarm robot coordination is to generate geometric patterns from the robots using a decentralized control approach. Such formations have numerous applications ranging from military to medical and space to underwater. The approach uses artiﬁcial force based controller which navigates the robots in a decentralized manner. The mathematical analysis of the controller for stability and cohesiveness provides a criterion for selecting the weighing parameters for the controller. Moreover, the extendability of the concept of artiﬁcial force based control of a swarm is demonstrated in an application speciﬁc scenario. Here, a two-stage controller which satisfy special control requirements of an airborne guided weapon system was derived. The requirement of simultaneous and delay-free data sharing is an absolute necessity for many mission critical robotic systems, such as map generating, search and rescue, space exploration, land mine detection etc,. The all-to-all wireless communication algorithm presented in this thesis provides an excellent media for sharing the mission critical information. Apart from that it also minimizes the energy consumption in communication by eﬀectively controlling transmission power while preserving the QoS requirements of the communication links. Furthermore, as a secondary result, the nodal energy saving algorithm for a single-hop wireless data collecting network was derived and experimentally veriﬁed. The outcomes of the entire research was presented cohesively as an application case study, which established the links in seemingly standalone research components. To my family Table of Contents Table of Contents vi Acknowledgements 1 Introduction 1.1 Background . . . . . . 1.2 Overview of the Study 1.2.1 Contributions . 1.2.2 Thesis Outline viii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Swarm Robots: An introduction 2.1 Related Research Topics . . . . . . . . . . . . . . . . . . . . 2.1.1 Aggregation and ﬂocking . . . . . . . . . . . . . . . 2.1.2 Pattern formation . . . . . . . . . . . . . . . . . . . 2.1.3 Interactions within the Swarm - Communication and 2.2 Coordination and control approaches in swarms . . . . . . . 2.2.1 Potential Field Based Approaches . . . . . . . . . . 2.2.2 Artiﬁcial Physics Based Approaches . . . . . . . . . 2.2.3 Behavior Based Approaches . . . . . . . . . . . . . . 2.2.4 Other Methods . . . . . . . . . . . . . . . . . . . . . 2.3 Mathematical Background . . . . . . . . . . . . . . . . . . . 2.3.1 Lyapunov Stability . . . . . . . . . . . . . . . . . . . 2.3.2 Complex Integration and Winding Number Theorem 2.3.3 Perron-Frobenius Theorem . . . . . . . . . . . . . . 2.4 Problem Statements . . . . . . . . . . . . . . . . . . . . . . 2.4.1 Geometric Pattern Generation Problem . . . . . . . 2.4.2 Communication problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 2 3 3 . . . . . . . . . . . . . . . Sensing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 8 8 10 11 12 12 14 15 15 16 16 18 20 20 20 22 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 24 25 27 28 29 33 38 41 42 . . . . . . . . 3 Geometric Pattern Generation in a Multiple Robot System 3.1 Mathematical Model . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Shape formation algorithm . . . . . . . . . . . . . . . . 3.1.2 Simulation results . . . . . . . . . . . . . . . . . . . . . 3.2 Behavior Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 X Swarm deﬁnition . . . . . . . . . . . . . . . . . . . . . 3.2.2 Cohesiveness . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 Comment on stable locations inside the shape . . . . . . 3.2.4 Discussion on Analysis . . . . . . . . . . . . . . . . . . . 3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 4 Application Case Study: Swarming Guided Weapons 4.1 Motivation and Background . . . . . . . . . . . . . . . . . . 4.2 Two-stage controller . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Horizontal Motion . . . . . . . . . . . . . . . . . . . 4.2.2 Vertical Motion . . . . . . . . . . . . . . . . . . . . . 4.2.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Analysis of Release Height and Weapon Behavior . . . . . . 4.3.1 Cohesive Stage . . . . . . . . . . . . . . . . . . . . . 4.3.2 Release Height . . . . . . . . . . . . . . . . . . . . . 4.3.3 Summery of the analysis . . . . . . . . . . . . . . . . 4.4 Discussion on Implementation Issues . . . . . . . . . . . . . 4.4.1 Controller Modiﬁcation for Practical Implementation 4.4.2 Implementation, Technologies and Error Models . . 4.4.3 Obstacle Avoidance . . . . . . . . . . . . . . . . . . 4.5 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . 4.5.1 Multiple Aircrafts Engaged in a Single Target . . . . 4.5.2 Single Aircraft Engaged in Multiple Targets . . . . . 4.5.3 Point Generated Shapes . . . . . . . . . . . . . . . . 4.5.4 Shape Transitions . . . . . . . . . . . . . . . . . . . 4.5.5 Addition/Removal of Agents . . . . . . . . . . . . . 4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Communication and Power Saving Schemes for the Swarm 5.1 Fully-Connected mesh network for eﬀective communication . . . . . . . . 5.1.1 Power Control in Wireless Networks . . . . . . . . . . . . . . . . . 5.1.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.3 Iterative Controller . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.4 Convergence of the controller . . . . . . . . . . . . . . . . . . . . . 5.2 A simple power control algorithm for mobile data collector based remote scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.1 Motivation and background . . . . . . . . . . . . . . . . . . . . . . 5.2.2 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.3 Path loss model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.4 Power control analysis . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.5 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Discussion of implementation considerations . . . . . . . . . . . . . . . . . 5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . gathering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 43 44 45 47 48 48 48 54 55 56 56 58 58 62 63 63 64 65 66 67 69 69 70 71 73 74 77 77 77 79 81 83 86 86 6 Concluding Remarks 89 Appendix I: Mathematical Function for Contour Generation 92 Bibliography 93 Acknowledgements Pubudu Pathirana has been more than a PhD supervisor to me at my time at Deakin University, he is an excellent adviser, not only in research but in the life too, and a good friend. His guidance in the life makes it easy to adapt to the new lifestyle in a foreign country and his guidance in research inevitably helped me to understand the intricacies in research and academia. His help in producing this dissertation is invaluable. My life in Australia could have been a havoc without the ﬁnancial assistance from Marimuthu Palaniswami (Department of Electrical and Electronics Engineering, University of Melbourne), who employed me as a research assistant to work on the same research project through the ARC network on sensor networks where Deakin is a partner. I sincerely thank D.C. Bandara (Department of Production Engineering, University of Peradeniya, Sri Lanka) and Sarath Seneviratne (Department of Mechanical Engineering, University of Peradeniya, Sri Lanka), who encouraged and guided me to start a PhD. Additionally there are many people in Deakin University who made my time enjoyable, I thank them all for the help and encouragement. Above all, I am thankful to my parents, Chandradasa and Chandraleela Ekanayake, and my wife Piyumi; who dedicate their entire time for me. Also I thank our daughter Anuki for being the prime reason to ﬁnish this thesis on time. This thesis is dedicated to them. viii Chapter 1 Introduction “Science is a mechanism, a way of trying to improve your knowledge of nature. It is a system for testing your thoughts against the universe, and seeing whether they match.” - Issac Asimov Nature provides us enough design examples to “innovate”; scientists understanding the natural wonders of the world and mimicking the natures’ designs had eﬀectively contributed in improving the quality of life of humans. Using natural resources to advance the life of the humans began in early days of farming based cultures, involving animals to perform the hard work for humans. Later people develop machineries to replace the animal labor and mimicking animal behavior and structure: tractors replacing hardworking animals (horses, cows etc); aero planes, naval ships, and submarines mimicking birds, aqua birds and ﬁsh are some examples. In modern days the research in robotics open new frontiers to involve natural wonders in improving the physical wellbeing of humans. 1.1 Background Swarm robotics, inspired by stability of the natural swarms (social insects such as ants, bees, termites, wasps, etc) that survived all the way from the beginning of life forms on earth, is an emerging area of research among robotic researchers across the world. This thesis is an attempt to extend some new concepts into the diverse research interests in swarm robotics. In this study, a scheme for navigation, shape formation and communication of a swarm of robots is developed enabling multitude of applications; ranging from medical to defense and space to underwater. Although swarm or multi-agent dynamic system concept, in general, is used in several disciplines, this work considers the multi-agent system as a collection of loosely coupled dynamic units moving in 2 or 3 dimensional space. In applications, the dynamic units can be robots, vehicles, UAVs, etc, where the motion dynamics is governed by a common control algorithm (decentralized or centralized). Multi-agent systems have been considered in range of applications such as; agent-based systems, self-organization, distributed artiﬁcial computing, evolutionary computing. Therefore some of the results in this study could be applied in many disciplines in multi-agent systems (other than the robotics), however we do not explore such extensions here. Robustness, ﬂexibility and scalability of multi-agent dynamic systems or swarm robots make them extremely suitable, but not limited, to application domains that have to cover a large area, tasks that are too dangerous and that need higher degree of maneuverability and dynamic scalability. This can not be accomplished by an individual agent or a monolithic system [1]. Such applications include; data gathering from a widespread area, monitoring systems which needs dynamically assigned positions (such as sea-bed monitoring, water quality monitoring in a lake, etc), de-mining (land mine removal) robot groups, search and rescue support (specially in collapsed buildings) and battle ﬁeld support (spying, maintaining dynamic communication links, etc). Moreover, the characteristics of swarm based dynamic systems have been extended due to some breakthrough technological advances in nano-scale robots and their biological counterpart “bio-Nano robots”. 1 2 Chapter 1. Introduction However, this technology has faced with the challenge of developing nano-scale actuators and sensor devices. With the advances in electronics and MEMS (Micro-Electro-Mechanical System) technology, the development of physical devices for micro-swarm robots has been making impressive progress in recent years, indicating an opening of a wide application spectrum for swarm robotics. As the review studies of [2, 3] suggests, main problem domains can be identiﬁed as; Coordination and control in pattern formation, coordinated movement, obstacle avoidance, foraging, self-deployment activities, and communication and sensing. Although many concepts were developed for maneuvering such swarm of robots, there has not been a “ﬁnal solution” for the multiple robot coordination problem. On the other hand, the communication within the robot group has also been investigated by many researchers, emerging numerous concepts varying from simple pheromone like communications to satellite based communications. As in the control and coordination problem domain, there has not been “the solution” for the communication problem, simply due to wide-spread application domains of the swarm robotics. 1.2 Overview of the Study This dissertation presents a decentralized approach for generating geometric patterns in a mobile robot group. Moreover, a communication scheme that facilitates the groups’ simultaneous communication requirements is introduced. This is crucial for eﬀective navigation of the robots. The study is mainly focused on a group of robots maneuvering in an outdoor environment, however the concept can be used for indoor robot group equipped with carefully selected communication and sensing devices. This study has two main aspects; 1. Developing a navigation scheme to guide a group of robots (agents) toward a target area, distribute them inside a given contour while eliminating inter-member collisions, 2. Developing a communication scheme to eﬀectively link the robots together which enables simultaneous communication without interferences. Apart from the above objectives, the study presents some secondary objectives as follows: 1. Based on the above controller, derivation of a secondary navigation scheme for controlling an airborne robotic swarm 2. Study of the control architecture in uncertainties in the sensing mechanism and modiﬁcation of the navigation scheme to deal with such uncertainties, obstacles and physical limitations of the robots. 3. Energy eﬃcient communication scheme for remote data collection from a already deployed static/mobile wireless sensor network. In achieving the above objectives, the following factors are considered; • Decentralized Behavior - The swarm operates in a decentralized manner such that it does not depend on external resources or commands. Here, communication with-in the group cannot be avoided in achieving a complex objective. However, the communication with-in the group must exhibit characteristics that enable achieving independent operation of individuals. • Simple Architecture - This denotes the sensing capabilities and system level functioning of individual units. However the degree of simplicity depends on the application and size of the robot. For example, disposable robots can be equipped with a low cost and relatively simple architecture whereas for mission critical robots (such as space exploration) more complex system architecture can be employed. • Scalability- i.e. the formation and navigation does not depend on the number of members; entail the reconﬁguration of the positions relative to each other. However, this has limitations (both lower Chapter 1. Introduction 3 and upper bounds for the swarm size) in real-life scenario; coverage/ working radius of individual members determines the lower bound and the physical size and maneuvering radius determine the upper bound. Furthermore, the number of members is determined by the limitations in communication too. The bandwidth and the speed of communication always have a trade-oﬀ between the size of the network (number of nodes). • Flexibility - i.e. the ability to adapt to new situations such as sudden change in shape, moving shapes etc which changes the stable conditions of the swarm. Like the previous case, this is also bounded by several factors; among them physical motion limitations (speed, power, etc.), communication limitations and localization-sensing limitations are signiﬁcant. • Robustness - The ability of the swarm to withstand undesirable changes in the environment (obstacles, communication failures etc.) and in the members (i.e. number of units, break-downs, etc) while achieving the underlying objective. 1.2.1 Contributions The contribution of this work is two-fold. A novel shape formation algorithm In the shape formation algorithm [4, 5, 6, 7], the members in the swarm are populated inside a given contour rather than arranging the members on the perimeter. The proposed scheme is decentralized such that it navigate to generate the objective formation without central coordination, either in the form of a base station or virtual leader. Moreover, the proposed architecture does not pre-determine the positions of the members inside the shape, thus the system is stable against changes in the swarm size and the shape of the contour as well as the changes in the environments such as obstacles. A novel concept of a fully-connected mesh network for robot communication This mesh network enables all the members in the network to communicate with each other, using a broadcast type fully-connected mesh network [8, 9]. Moreover, the study provides an upper bound in the capacity of the network in terms of the number of wireless nodes. Since the network does not perform a peer-to-peer type communication, the scalability, ﬂexibility and robustness characteristics of the swarm are well preserved. 1.2.2 Thesis Outline This thesis is organized as follows. Chapter 2 provides an overview of the multiple robot shape formation and path planning problem with a comprehensive analysis of related works in the ﬁeld related to this study. Moreover, the theoretical background of the techniques used in the remaining chapters are presented. Chapter 3 introduces the basic robot navigation and shape formation architecture together with a theoretical analysis on the behavior of the mobile agents under the proposed scheme. Computer simulation case studies are also presented to verify the analytical assertions. Chapter 3 serves as a foundation for the next chapter where the proposed architecture is used/modiﬁed for speciﬁc application scenarios of multiple mobile agent navigation in shape formation. Chapter 4 presents an application of the multi-agent control system using an air borne guided weapon system. Here the control algorithm is modiﬁed as a two stage controller in order to minimize possibilities of collateral damage. The simulation case studies for multiple weapon navigation verify the eﬀectiveness of the controller. Moreover, an improved version of the controller is presented subsequently where the restrictive assumptions made for deriving the shape formation algorithm proposed in chapter 3 are relaxed. The practical implementation issues of the navigation algorithm are discussed and simulation case studies were presented which closely resembles real-world scenarios in self-localization, communication etc. 4 Chapter 1. Introduction Chapter 5 introduces a spread spectrum all-to-all communication scheme for simultaneous communication within the robot group. Moreover, this scheme maintains the minimum possible power consumption in the entire group while ensuring clear communication links (i.e. without interferences). The algorithm was evaluated using simulation case studies. Further we present a transmission power control algorithm which maintains the optimal Co-channel Interference Ratio (CIR) for energy critical devices communicating with a single base station. The proposed algorithm can eﬀectively be used for mobile data collector based sensor network deployed using an airborne swarm architecture introduced in the chapter 4. It argues that the energy consumption of the proposed algorithm is comparable to other power control algorithms in literature. Chapter 6 provides conclusions on multi-agent research and directions for further work in the ﬁeld. Here we present an overview of the research in application framework which provides the connectivity between diﬀerent topics covered in the study. Chapter 2 Swarm Robots: An introduction “If every tool, when ordered, or even of its own accord, could do the work that beﬁts it... then there would be no need either of apprentices for the master workers or of slaves for the lords.” - The Greek philosopher Aristotle Robotics and automation of processes are long sought subjects in the human history. Automation applications date back as far as 4th Century BC, when the Greeks used water clock with movable ﬁgures. Evidence of humanoid robots ﬁrst encounter in Islamic Golden Age (from the middle of the 7th century to the middle of the 17th century) when the Arabic inventor Al-Jazari created the ﬁrst programmable humanoid robot in 1206. Al-Jazari’s automation was originally a boat with four automatic musicians that ﬂoated on a lake to entertain guests at royal drinking parties [10]. Moreover, “The Book of Knowledge of Ingenious Mechanical Devices” by Al-Jazari (1206), reveal several other automation/ robot devices that he invented in the early ages of robotic science. In the western world the written history of robotics arises with the great philosopher Leonardo da Vinci who designed a range of automated machineries for day-to-day life which were found as note book sketches. One of the ﬁrst documented design of a humanoid robot called “Mechanical Knight”, was among them, and later it was reconstructed as a miniature version [11]. Among the other early developments in robotics; “Moving anatomy” the mechanical duck by Jacques de Vaucanson (1738), Designs by Hisashige Tanaka (Karakuri Zui “Illustrated Machinery” was published in 1796), Nikola Tesla’s radio-controlled (tele-operated) boat etc; represents major milestones. The word “Robot”, which originates from a Czech word for labor, was ﬁrst used by Karel Capek on his play Rossum’s Universal Robots [12]. Since then many science ﬁctions used the term “Robot” to deﬁne artiﬁcial life and intelligent machines. Issac Asimov (1920-1992) was among the pioneers of the science ﬁction writers who popularize the word robot in early stages. Also he deﬁnes four rules to be used for robot human interactions and still the same rules are accepted globally. Since the “Unimate”, the ﬁrst industrial robot (developed for the General Motors assembly line in 1961), robotics gain a rapid development inspired by the development of electronics technology. Miniature Robots The concept of miniature robots emerged with the application of robotic devices in the medical, defense and exploration ﬁelds. Applications such as diagnosing and delivering medications to inner body organs, land mine detection, exploration of unknown/hostile terrains (battle ﬁelds, collapsed buildings, ocean bed and extra-terrestrial planets) etc; have distinct advantages in employing small, low cost (sometimes disposable) robots compared with large expensive robots. In general, such system can be eﬀectively employed in situation where: the task covers a region (environmental monitoring - resembling a mobile sensor-network), tasks that are too dangerous (working in an unknown/hostile environment where some units may destroy), tasks that scales up or down in time, tasks that require redundancy or a mixture of the above conditions occur (see [1]). However, the control and coordination of such small robotic devices to perform a complex task remain a problem for years. Following some interesting studies on social insect 6 Chapter 2. Swarm Robotics: An Introduction 7 Figure 2.1: Some Designs from Leonardos’ Sketches - From left, (1) A sketch of a automated machine gun [13] (2) The outer appearance of the “Mechanical Knight” and (3) the inner mechanism of the knight controlling the arms [14] behavior, robotic scientists developed a new conceptual framework for cooperative miniature robots called “swarm robotics”, which behave like natural swarms such as ants, bees, wasps etc. Sahin in [1], formally deﬁnes the term “Swarm Robotics” as: “Swarm Robotics is the study of how large number of relatively simple physically embodied agents can be designed such that a desired collective behavior emerges from the local interactions among agents and between the agents and the environment.” Other than that, Gazi and Fidan in [3] describes the swarm or a multi-agent dynamic system as: “A network of a number of loosely coupled dynamic units that collectively reach goals that are diﬃcult to achieve by an individual agent or a monolithic system.” Distinctive features like decentralized behavior, group learning and distributed sensing demonstrated in such systems make the robots capable of operating in highly hostile environments and unpredictable circumstances, where centrally controlled robotics systems can simply loose their communications with the base station. The limitations in computational power, sensing and communication capabilities in small scale units (especially in micro and nano scale systems) holds a huge barrier against rapid development of this technology. However, with recent advances in communication, networking and computing, multiagent systems have generated a renewed interest among researchers across the world. Moreover, studies on natural swarms have provided the robotics community a great conceptual basis in developing control algorithms for decentralized multiple robot coordination. Natural to Artiﬁcial Swarms Mankind gained a great deal of knowledge by studying the wonders of the mother nature: from a simple tent to a gigantic space station, from a simple hand tool to a large computer network that binds the world together, there exist the lessons obtained from the nature. There is no exception to the robotics, especially swarm robotics; studies on animal behavior had a lot to share with robotics researchers who were developing machines to make the life of humans easier. From pre-historic times, the studies on social insects and birds created the traditional knowledge on natural disasters and weather predictions. Natural swarms or social foraging animals can be observed in land, air or water. Specially the behavior of insects and other smaller species (such as ﬁsh, birds etc) inspired many biological researchers, due to their organized behaviors despite the smaller brain size and limited sensing capabilities. The robustness, scalability and ﬂexibility of the autonomous behavior (without central control) in such a group of insects in achieving complicated tasks (nest building, food ﬁnding, attacking enemies etc) contributed many new concepts in artiﬁcial intelligence [15, 16, 17], optimization [18, 19, 20, 21] and robotic sciences [1, 22, 23, 24]. Many researchers studied group behavior of animals such as organization of work in ant colonies [25], social foraging models in ﬁsh [26], navigation and signaling methods used by ants [27] and in [28] shoaling behavior of ﬁsh with respect to performing an escape mechanism. Mathematical models for the group 8 Chapter 2. Swarm Robotics: An Introduction behavior developed by Inada in [29] and algorithms governing schooling behavior of ﬁsh presented by Grunbaum et al.[30] etc, have inspired the robotics researchers into more reﬁned approaches in swarming techniques. For example Keller et. al in [24] analyzed the properties of robot groups having ant-like decentralized behavior when performing tasks in a collaborative fashion. In [31], the authors present a collaborative cleaning algorithm for a group of robotic vehicles, called “Blind Bulldozing”, which is based on site preparation of wasps. In the robotics point of view, the study on ﬂying patterns of a ﬂock of birds by Reynolds [32] becomes the ﬁrst of such study which created a mathematical model for the decentralized behavior of a animal group. In his study, based on biological research studies on the bird and ﬁsh behaviors [33, 34], the ﬂying model uses inter-member communications for collision avoidance and vision-based sensing capabilities. Even though this model is not practical for using directly for actual robotic units, it created a renewed interest among robotic researchers to investigate social insect behaviors to be used in distributed robotic systems [3]. 2.1 Related Research Topics The swarm robotic systems and multi-agent dynamic systems have a vast range of research topics and many of them are associated with the behaviors of social insects. However this section presents the topics / problems that are relevant to our study. Reviewing the past research literature, several main problems can be identiﬁed with respect to control and coordination of a mobile robotic swarm, namely aggregation and ﬂocking, and pattern formation. In addition to the above, interactions among the robotics group, i.e. communication and sensing, can be considered as other problem area which relates this thesis. In the rest of this section, we review some of the relevant past research related to our work. 2.1.1 Aggregation and ﬂocking In a biological perspective, aggregation (gathering together) is a basic behavior which is demonstrated during social foraging. Social foraging is basically used to increase success rates in diﬃcult tasks such as food ﬁnding, attacking enemies which could not be accomplished by a single entity. On the other hand, ﬂocking is the collective motion behavior of a large number of interacting agents/robots with a common objective, which is a highly demonstrated feature in natural swarms such as birds. Therefore, the swarm robots deployed in similar missions will essentially demonstrate social foraging behaviors. Aggregation Artiﬁcial potential ﬁeld based methods can be considered as the most popular approach in swarm aggregation studies. Inspired by the studies on mathematical modeling and simulation of aggregation in biological swarms [35, 36, 37, 38], Gazi et.al. [39, 40, 41, 42] performed rigorous mathematical analysis on the stability of aggregation of swarms using inter-member artiﬁcial attraction/repulsion potential ﬁeld based model. For example, [40], which is the ﬁrst of the stability analysis studies by Gazi, used the attraction/repulsion function; y2 (2.1.1) g(y) = −y a − b exp − c where the motion of an individual agent is modeled by, i x˙ = M g(xi − xj ), i = 1..M. (2.1.2) j=1,j=i Here xi ∈ Rn represents the position of member i and M is the group size. Here the attraction/repulsion function g(·) represents an artiﬁcial social potential function derived from the studies on aggregation behaviors of biological swarms [37]. In this study Gazi and Passino showed that all the members of the above swarm moves toward it’s center of mass (¯ x) and all the members converge into a circle with radius Chapter 2. Swarm Robotics: An Introduction 9 2 1 b(M − 1) c T exp(−0.5), within a ﬁnite time bounded by − ln , where Vi = (1/2)ei ei = aM 2 2a 2Vi (0) and ei = xi − x ¯. Based on the above studies, in [43, 44, 45] the concept was further enhanced to deal with the stability of aggregation in diﬀerent situations such as presence of noise, sensor uncertainties and measurement errors. The control architectures of the artiﬁcial potential ﬁeld based approaches are discussed in detail in the section 2.2.1. Apart from artiﬁcial potential ﬁeld approaches, behavior based and neural network based methods are among few successful approaches in achieving swarm aggregation. Soysal and Sahin in [46] introduced a behavior based generic aggregation method using simple probabilistic behaviors of the agents; obstacle avoidance, approach, repel and wait. In this study they conducted systematic experiments to investigate the behavior of the controller in achieving the aggregation where the robots are using an acoustic sensor to approach or repel from the loudest sound. Similarly Trianni et al., [47] tried to solve the aggregation problem employing a probabilistic controller using a higher level of abstraction than the sensor readings and actuator commands. In that study they deﬁned a probability matrix to deﬁne the probability of switching between behaviors (abstraction of actuator commands) in all the contexts (abstraction of sensor data) and observed the aggregation is possible with a predetermined matrix in a simple sensor-based simulation environment. While a rather diﬀerent approach was introduced by Naruse et al [48] for aggregation of multi-agent system; they used emotion-like two dimensional inner state and aﬀection-like subjective evaluation of others to perform aggregation behavior. Bahceci and Shain in [49] study the use and eﬀectiveness of evolutionary methods for developing neural network based controllers for agents in an aggregative swarm robotic system. They tried to achieve aggregation by evolving weights of a neural network with 12 inputs (four inputs to encode the sound values obtained from the speaker and the remaining inputs encodes the infrared sensor readings) and 3 outputs (one for the omni-directional speaker and the other two for controlling the wheels of the robot). Similarly, Trianni et al. in [50] used genetic algorithms to evolve the aggregation behavior by evolving the the weights of a perceptron. Flocking To the best of the authors knowledge, the ﬁrst extensive study in mathematically modeling of a ﬂocking behavior is by Reynolds in [32], where the ﬂocking behavior of birds were simulated in computer. In that study, Reynolds has proposed three basic behaviors for agents which contributes to a global ﬂocking behavior, namely (i) separation (Collision avoidance: avoid collisions with nearby ﬂock-mates), (ii) Alignment (Velocity matching: attempt to match velocities with nearby ﬂock-mates), and (iii) cohesion (Flock centering: attempt to stay close to nearby ﬂock-mates). These three simple rules have been used to develop realistic computer simulations for the ﬂocking behavior of birds. This study was further investigated by Vicsek et al., in [51], in which a self-propelled particle model was used to study the eﬀects of noise on the complex particle systems and phase transition from disordered to ordered states. The ﬂocking models in [32, 51] used “nearest neighbor rules” (where agents adjust their motion based only on their nearest neighbors) to achieve global ﬂocking in the absence of centralized coordination and time varying environments. This concept was further investigated in [52], where a mathematical analysis of achieving a common orientation during ﬂocking behavior was performed. Further improving the “nearest neighbor rules” concepts, Olfati-Saber in [53] introduces an algorithm for stable ﬂocking of agents with point-mass dynamics. In this study he used “nearest neighbor rules” and potential functions for aggregation and alignment, and provided a comprehensive analysis on the stability of the ﬂocking algorithms namely free-ﬂocking (ﬂocking where obstacles are not present) and constrained ﬂocking (in the presence of obstacles). Apart from the above, Tanner and coworkers in [54, 55, 56] presented ﬂocking behaviors based on artiﬁcial potential ﬁelds (which depends on the distance between two agents). In [55, 56], they performed extensive analysis of the ﬂocking behavior for systems with point-mass dynamics and in [54] for a system with non-holomonic unicycle dynamics. Rendezvous, on the other hand is another aspect of ﬂocking of natural swarms, which is demonstrated 10 Chapter 2. Swarm Robotics: An Introduction in birds, ﬁsh and mammals; can also be considered as a special form of ﬂocking, where robots are coordinated to meet at a point or small region [57, 58]. As Lin [58] and Ando [57] proposed in, in the Rendezvous problem, each robot tracks the position of neighbors and updates the controller accordingly. Here the neighborhood is deﬁned such that a robot i (Ai ) can sense the robot j (Aj ), if the distance is less than a constant V and if there is no obstacle in between, i.e. the neighborhood of i (Si ) at time t is deﬁned as; Si (t) ⊆ (Aj |j = i, xj (t) − xi (t) ≤ V ), where xi represents the position vector of robot Ai . Solutions and mathematical analysis to this problem are provided in [58, 59, 60, 61]. 2.1.2 Pattern formation According to Bayindir and Sahin [2] pattern formation can be deﬁned as the emergence of global patterns from local interactions among agents. However Gazi and Fidan in [3] deﬁned pattern formation in more generalized form and they introduced three main components of pattern formation; namely (1) formation stabilization and acquisition, (2) formation maintenance and cohesive motion control, and (3) formation reconﬁguration and switching. Pattern formation is a widely observed behavior in natural swarms; for example, a ﬂock of birds in long haul ﬂights generate a “V” shaped formation in order to minimize the air resistance and fatigue of physically weak birds. And it consists of distinct advantages in artiﬁcial swarms or swarm robotics too, facilitating easy maneuvering of the whole swarm when it comes to path planning and strategic positioning (especially in military applications). Unlike in aggregation, the controllers for pattern formation need a formation goal and a control algorithm to achieve that goal, thus consists of a more complex control architecture. In the pattern generation literature for robotic swarms, several approaches can be identiﬁed [62], however in this discussion we classify them into two broad groups based on the control and command perspectives; namely heterogeneous control and homogeneous control. In this discussion, the heterogeneous control means that the robots/agents are controlled by diﬀerent command/objective algorithms, and in the homogeneous controllers, every robot/agent in the group uses the same controller and the objective function. Note that in this discussion we are only considering the decentralized control structures, where the members of the swarm do not get control inputs from outside sources, except the objective functions and sensing (such as location information via RF links, vision based information, proximity information etc.). However, there exists some centralized control approaches investigated in the swarm literature, for example, Antolline et. al. introduced a control algorithm for a group of robots in [63] where the control commands are send from a base station/ control center. Among heterogeneous control strategies, leader based control [64, 65, 66, 67, 68, 69], where a virtual leader having a “higher level controller”, which includes the global objective functions, and a group of followers with a “lower level controller”, which is basically to follow the leader and depends on the control commands from the leader, is a common approach. This approach can also be considered as a semicentralized control approach for pattern formation, since the group is getting commands from the leader (central controller) or based on the behavior of the leader. Another approach in heterogeneous control is the speciﬁc positioning where the objective coordinates of each robot is given before hand, thus each controller consists of diﬀerent objective functions. In this approach, the formation is predeﬁned and the members are navigating to occupy the pre-deﬁned positions [69, 70, 71]. Various control techniques are developed to achieve the above objective, among them the behavior based approaches [72] and graphtheory based approaches [52, 53, 65] are signiﬁcant. Main drawbacks in this approach is that the formation is not scalable and it does not conform with the swarm robotic deﬁnitions, due to robustness and ﬂexibility issues. However this approach is the most reliable one in generating an exact pattern/formation. In the latter approach (homogeneous controllers), a common function is used to navigate the entire swarm and the system is highly scalable. Among early studies the geometric pattern formation algorithms introduced by Sugihara and Suzuki in [73] is a landmark study in which they used a simple control structure to control the robot behavior. In that study they presented algorithms to generate; circles (two cases, gathering the robots on the perimeter and populate the circle with robots - FILLCIRCLE ), polygons (two cases, on the perimeter and populate - FILLPOLYGON ) and line segments (based on a decentralized control algorithm). The control algorithms are extremely simple; for example in the circle Chapter 2. Swarm Robotics: An Introduction 11 generation algorithm, a robot R continuously monitor the positions of a farthest robot R and the nearest robot R , breaking ties arbitrarily, and moves as follows in real time; • Case 1: if d > D, then R moves toward R , • Case 2: if d < D − δ, then R moves away from R , • Case 3: if D − δ ≤ d ≤ D, then R moves away from R , where d is the distance between R and R , δ > 0 is a small constant and D is the diameter of the proposed circle. They have used simulation case studies to evaluate the proposed algorithms. Based on the above, Susuki and Yamashita [74] extended the study to investigate convergence and formation problems, and obtained generalized results for geometric pattern formation issues for a group of mobile robots. In recent studies for pattern generation, the artiﬁcial potential ﬁeld based methods, and behavior based methods have become increasingly popular. The control techniques for these approaches will be discussed in detail in the section 2.2. 2.1.3 Interactions within the Swarm - Communication and Sensing Swarm robotics is not always about the control and coordination of mobile agents, it entails the development of infrastructure for proper functioning such as communication, sensing, processing, power trains etc. In this section we discuss the studies focused on the communication and sensing for multiple agent systems or interactions within the swarm. As Bayindir and Sahin classiﬁed in there review study [2], the studies on interactions in robotic swarms can be divided into two categories; Interaction via Sensing and Interaction via Communication. Although the discrimination between the two can be diﬃcult, they propose a guideline based on the information sender side as follows; if the sender in the interaction aims to give information to other robots intentionally then that study is categorized as “interaction via communication” instead of “interaction via sensing”. On the other hand, if robots are sending information packets (broadcast or personalized) or interacting to show their status, i.e. switches on/oﬀ lights etc, then those are considered to be the type of “interaction via communication”. Interaction via sensing is basically the discrimination of other robots with the environment and is alternatively called as kin recognition. Kin recognition is an important feature of animals in nature. With the help of kin recognition they can perform collaborative tasks and protect themselves from their enemies better. In swarm robotic studies [50, 75, 46], kin recognition is used as a communication medium since some problems (e.g. ﬂocking, chain formation etc) in swarm robotics require discrimination of the robots in the environment to obtain acceptable performance. In this dissertation we do not review the previous studies in the above research area, “interaction via sensing”. However in the following discussion we brieﬂy discuss the major communication approaches which can be categorized under “interaction via communication”. A more advanced swarm robotic system, may require direct communication between robots in the form of broadcasting or one-to-one communication. In most of the swarm studies [39, 40, 41] authors assume that the swarm has a mean of communicating / sharing valuable information such as state information, however they do not elaborate the underlying communication protocol. While some studies give more information on the communication architecture than the control aspects of the robots. For example, Nouyan and Dorigo in [76] implemented a chain formation behavior using a status indication in the form of a LED ring around their body. In that study the colors of the LED ring (red, green and blue) indicate diﬀerent status of the member and it can be used by the neighboring robots to determine their activities. Similar to above, Grob et al., [77] studied a self-assembly problem in which the robots discriminate the members connected to the seed using a bi-color LED ring around their body. Apart from the above there exists some studies where the communication / interaction uses the environment as the communication media, which are categorized as interaction via environment [2]. These studies are based on the communication approaches used by biological swarm, such as pheromone communication of ants. Pheromones is a chemical that ants lay on the ground. When an ant ﬁnds food, it will leave a trail along the ground on its way back to home, which in a short time other ants will follow. 12 Chapter 2. Swarm Robotics: An Introduction In the swarm robotic studies [78, 79, 80, 81] the same concept was used for communication in a robotic swarm where they used artiﬁcial pheromones. In the swarm robotic literature, one could not ﬁnd a wireless communication approach (i.e. Infrared or RF based) explicitly for swarm robots. However the studies in wireless sensor network, where adhoc connected set of node communicate with each other to share valuable information, can be used for communication within a robotic swarm. A review of such communication methods developed for wireless sensor networks is presented in chapter 5. 2.2 Coordination and control approaches in swarms Swarm robotics and the rest of the robotic systems can be clearly distinguishable based on the control architecture. The autonomous behavior of agents without a central control is the key factor in a robotic swarm. The central control based robotic groups (which includes leader based strategies) are prone to many drawbacks; such as higher computational cost and complexity, sensitivity to loss of some agents (e.g. leader/central commanders in leader based systems), communication delays between the control center/leader and the other agents, feasibility of processing entire network information by the central unit. These are disadvantageous to operate in hostile and changing environments[3]. However, one can observe that there is signiﬁcant number of literature on centralized control architectures of swarm robots (see [63, 64, 65]). In this section we brieﬂy discuss the major control and coordination approached found in swarm literature, while mainly concentrating on approaches similar to ours [4, 5, 6, 7]. 2.2.1 Potential Field Based Approaches Use of artiﬁcial potential ﬁelds for multiple robot navigation, ﬁrst introduced by Reif and Wang in [82], have been extensively studied in the literature [39, 40, 41, 83, 84, 85]. Among them Gazi, Passino and the co workers had done extensive study on the social potential functions [39, 40, 41, 42] for swarm aggregation, which were based on the behaviors of biological swarms in ﬁnding food or nutrients [38, 37]. In these studies [42, 41], the swarm is navigated using a control function as below, (2.2.1) x˙ i = −∇xi J(x), i = 1, . . . , N, where xi ∈ Rn denote the position vector of an individual i and x = [x1 , . . . , xN ] denote the position vector of all the agents in the swarm. Here J : RnN → R is the potential function and can contain a social potential function component (see [41]) as well as a environmental potential function component (see [42]). Thus can be shown as; J(x) = N i=1 Jenv (xi ) + N −1 N Jij (xi − xj ), (2.2.2) i=1 j=i+1 where Jij represents the social potential function which controls the mutual attraction/repulsion behavior of the agents and the Jenv represents environmental/external potential function. For a stable swarm aggregation, they provide some conditions for the Jij as; (i) The potentials Jij (xi − xj ) are symmetrical and satisfy ∇xi Jij (xi − xj ) = −∇xj Jij (xi − xj ) ij ij : R+ → R+ such that ∇y Jij (y) = ygar (y) (ii) There exists a function gar ij ij (y) = 0 and gar (y) > 0 for y > δij and (iii) There exists unique distances δij , at which gar ij gar (y) < 0 for y < δij . The potential function component Jenv is derived from biological swarms and represents the attraction/repulsion proﬁle or the “σ-proﬁle” which can be the proﬁle of nutrients, or some attractant or repellent substances. This work was further investigated by Yang and Passino in [44] where they derive a control strategy for social foraging of agents with point mass dynamics in a noisy environment including uncertainties in Chapter 2. Swarm Robotics: An Introduction 13 the sensing environment as well as the relative positions between agents. In addition to the controller used in [41, 42], the agents in this approach tries to move toward the center of the swarm and match its velocity with the average velocity of the group. The motion of the swarm in [44] was controlled by; x ¨i = −kpi eˆip − kvi eˆiv − kv i − ∇xi J(x), i = 1, . . . , N (2.2.3) where, eˆip = eip − dip and eˆiv = eiv − div . In above expression dip and div represents the uncertainties in ¯, eiv = v i − v¯ are relative position and velocity of position and velocity measurements, and eip = xi − x ith agent with the center of the swarm (¯ x, v¯). The ∇xi J(x) in the above represents the noisy gradient, which is similar to that of [41, 42]. They have shown that the above swarm demonstrates stable foraging despite the uncertainties in sensing/measurements. Similar to above study Olfati-Saber in [53] introduced a control strategy for swarm aggregation where the velocity matching term is matching the velocities of the neighboring members only. This is based on the ﬂocking algorithm of Reynolds [32]. The velocity matching part of the controller (uvi ) is in the following form; kvij (x)(v i − v j ), i = 1, . . . , N. (2.2.4) uvi = −mi j∈ℵi Here the neighboring members of i are deﬁned as; ℵi = {j ∈ V : xi − xj < r}, where r ∈ R+ . Similarly to the attractive/repulsion functions in [86, 41, 42, 44, 53], artiﬁcial potential functions are being used for swarm aggregations, formation and other multiple-robot coordination and control tasks. Some of the work directly address the issues of collisions between agents, using unbounded repulsion functions to guarantee collision avoidance [86, 87], where the inter-individual repulsion force is in the form of; c , (2.2.5) gr (xi − xj ) = i x − xj 2 which goes to inﬁnity as the distance between two members approaches zero. Moreover, researchers investigate numerous issues in a swarm using a potential ﬁeld based controller, such as cohesiveness of the group, bounds of the swarm size and the motion of the group achieving the objectives (formation, ﬂocking). Lyapunov-like methods are usually used for analysis resulting in conservative bounds. Furthermore, in the analysis, some studies [40, 41, 86, 44] assumed that each individual agent knows the relative positions of the entire swarm, which become unrealistic for biologically inspired control approach. In a biological swarm, each agent can only observe the positions of the neighboring members, which is the case with the Reynolds approach [32]. In all above control approaches the swarm is modeled to have higher-order agent dynamics, i.e. point mass dynamics and single integrator model (see Remark 2.2.1), where the motion dynamics of the agent does not correspond to any real-world vehicle or a motion platform. However, the results obtained are of high value, since given the motion characteristics of the swarm, one can design a controller so that it works as with higher-order models. Sliding mode control is a such approach in which a switching controller with high enough gain is applied to suppress the eﬀects of modeling uncertainties and disturbances, and the agent dynamics are forced to move along a stabilizing manifold called sliding manifold. Gazi in [41] used a similar technique to control a swarm with fully-actuated agent model with uncertainty (see Remark 2.2.2). In the sliding mode control approach, it is possible to design each of the control inputs ui to enforce satisfaction of the trajectories generated by the higher-level models and therefore recover from the deﬁciencies due to mismatching between the actual and modeled agent dynamics [41]. The sliding manifold used in [41] is in the following form, si = x˙ i + ∇xi J(x) = 0, i = 1, . . . , N, (2.2.6) where x = [x1 , . . . , xN ]. Then by choosing the control inputs as; ui = −ui0 (x)sign(si ) + fik (xi , x˙ i ), (2.2.7) 14 Chapter 2. Swarm Robotics: An Introduction where sign(si ) = [sign(s1 ), . . . , sign(sN )] , and choosing gain ui0 (x) of the control input as ui0 (x) ¯i >M 1 ¯ i i i fi (x , x˙ ) + J¯i (x) + , Mi (2.2.8) ¯ i , M i and f¯i (xi , x˙ i ) are one can guarantee that si s˙ i < −i si and that sliding mode occurs. In above M ¯ the known bounds on the uncertainties and disturbances, Ji (x) is the computable bound on the potential function derivative and i > 0 is an arbitrary constant. Remark 2.2.1. In the single-integrator motion model, the motion of the ith agent is given by x˙ i = ui . In 1 ¨i = i ui . Here mi is the mass of the the point-mass dynamics, the motion of the ith agent is given by x m agent and ui represents the control input for the agent. Remark 2.2.2. The fully actuated agent model is a more realistic model for agent / robot / vehicle dynamics than single-integrator and point-mass models and the motion of such system is governed by; ¨i + f i (xi , x˙ i ) = ui , i = 1, . . . , N. mi x (2.2.9) Here, xi , mi and ui represent the position, mass and control input of the agent respectively, and f i (xi , x˙ i ) ∈ R represents the centripetal, Coriolis, gravitational eﬀects and additive disturbances. 2.2.2 Artiﬁcial Physics Based Approaches Artiﬁcial physics based approach for control and navigation of multiple robots is introduced by Spears and Gorden in [88], and further enhanced by Spears, Spears-Gordon1 and co-workers in [88, 75, 89, 90, 91, 92, 93]. In the review study [3], Gazi and Fidan classify this approach as a subclass of the potential ﬁeld based control approaches. Artiﬁcial physics framework, alternatively called “physicomimetics”, is based on the fundamental laws of physics, particularly mechanics such as Newton’s laws of motion, and the robotic behaviors that are similar to those shown by solids, liquids, and gases. They proposed solid formations for distributed sensing tasks, liquids like behavior for obstacle avoidance tasks and gas like behavior for coverage tasks, such as surveillance and sweeping. The concept behind the “physicomimetics” framework is elegantly simple. In essence, virtual physical forces drive a multi-agent system to a desired conﬁguration or state. The desired conﬁguration (state) is a one that minimizes overall system potential energy - similar to the artiﬁcial potential ﬁeld framework. In macroscopic level, the system acts as a molecular dynamics (F = ma) simulation. At an abstract level, artiﬁcial physics treats the agents as physical particles (point mass agents) in a 2D or 3D space. In their framework, the state of each particle (agent) is calculated using the laws of physics at each time step, based on the forces applied to a particular agent. Moreover, they have used novel methods for the analysis, which diﬀers from Lyapunov based methods, common in artiﬁcial potential ﬁeld based approaches [39, 40, 41]. In some cases provides experimental evidence of the system behavior using small inexpensive robots [75]. Another important aspect in their study is the chemical plume tracing [92, 93, 91] which is particularly important in security and surveillance applications. In their basic framework they deﬁned an inter-agent attractive/repulsive function; Fij = Gmi mj ≤ Fmax p rij (2.2.10) where G is the “gravitational constant”, mi , mj are the masses of agents i and j, rij is the distance between the agents i and j, and p ∈ [−5, 5] is a user-deﬁned variable. Moreover, they have deﬁned that the force Fij is attractive when r > R and repulsive when r < R. In above equation Fmax represents the maximum force that can be applied on any particle. 1 Diana Gordan later become Diana Spears Chapter 2. Swarm Robotics: An Introduction 2.2.3 15 Behavior Based Approaches Another common approach for multiple robot coordination is the behavior based approach [32, 72, 46, 48, 49, 94] or artiﬁcial life based systems, where various behaviors determine the interactions between the agents / robots. The ﬂocking simulation by Reynolds [32] is one of the ﬁrst studies of swarming using a behavior based approach (see section 2.1.1 for details). After that, the work done by Balch and Arkin [72] holds a benchmark in behavior based multiple robot coordination. In that study they controlled a team of real vehicles using reactive behaviors for formation motion and to reach navigational goals including collision avoidance with other robots as well as obstacles. In [72], the authors considered several formation patterns for a four-robot team namely line, column, diamond and wedge formation. In the control algorithm, each robot computes its desired position in the formation based on the locations of the other robots. Three techniques are considered in this study for formation position determination: (i) unit center referencing (each robot computes the unit center independently by averaging positions of all the robots), (ii) Leader referencing (each robot determines its formation location with respect to the leader) and (iii) Neighbor referencing (each robot maintains its position relative to a preassigned neighboring robot). Apart from that Balch and coworkers in [94] conducted an extensive study on behavior based navigation/control of multiple robotic systems using social insect behavior. Other than formation control and ﬂocking of multiple agent system, behavior based systems were used for the aggregation in a swarm robotic system. Soyal and Sahin in [46] used a ﬁnite state machine with diﬀerent probabilities (as the behavior switching mechanism) to determine three basic behaviors of the robot team, namely approaching, repelling and waiting. Similarly, in [49] Bahceci and Sahin used a neural network controllers for generating aggregation behaviors. Here the performance of the simulated robotic swarm in controlled by neural network controllers tuned by genetic algorithms and is systematically studied by diﬀerent parameter settings. While a rather diﬀerent approach was introduced by Naruse et al in [48] for aggregation of multiagent system; they used emotion-like two dimensional inner state and aﬀection-like subjective evaluation of others to perform aggregation behavior. In [48], they deﬁned an agent as; Agenti = (Aij , Eik , Pi ) (2.2.11) where Aij ∈ [−1, 1] represents the aﬀection value of the agent i to the agent j, Eij ∈ [−1, 1] represents the emotion value of agent i to the agent j and Pi represents the position of the agent in two-dimensional space. Here, the authors showed that the aggregation strategy and properties can be changed by altering the aﬀection values. Moreover they evaluated the application of the control strategy to the box moving problem via simulation case studies. Apart from the above, in [95], the authors considered the application of Lyapunov stability techniques to the design of motor scheme in a behavior-based setting. 2.2.4 Other Methods In this section we summarize few other control approaches that are commonly used in the literature. We do not elaborate these methods since they do not relate to the study presented in this dissertation. Probabilistic or non-spatial approaches are also used for controlling/modeling swarming behaviors. From the biological literature, several examples can be found for modeling biological systems in probabilistic manner. In [96] the authors present a general continuous model for animal group size distribution. In [46, 97, 98], probabilistic approaches were introduced in aggregation and navigation of swarm robotic systems. It can also be observed that, Lyapunov based methods were used for the stability analysis of artiﬁcial potential ﬁeld based controllers. However there exists few studies in which Lyapunov based techniques, particularly so called control Lyapunov functions [99] are used at the controller design stage [100, 101]. Apart from Lyapunov based techniques, control graph (a combination of non-linear control theory and graph theory) based swarm coordination were also studied [102, 103, 104, 105]. In some studies 16 Chapter 2. Swarm Robotics: An Introduction Stable Asym ptotically Stable R O r S(R ) S(A) U nstable H (R ) x0 S(r) H (A) Figure 2.2: Stability Regions in the Lyapunov Method [102, 105] a leader based formation control systems (moving reference) were used while in some others [103] distributed control techniques were used. The virtual leader concept is also a common approach in multiple robot formation control and in some studies the virtual leader controls the other members of the group while in others the virtual leader acts as a moving reference point that inﬂuences the member in its neighborhood [67, 65, 72]. Besides the work mentioned above, various other approaches can be found in the literature in nonlinear control frame works, such as neural networks, dynamic inversion, back-stepping, adaptive control, output regulation etc. However we avoid the details of the control strategies and models involved in them. 2.3 Mathematical Background The multiple robot coordination and communication architecture introduced in this thesis uses several mathematical concepts in deriving the control algorithms and in the analysis sections. This section presents a basic introduction for some underlying mathematical and analytical techniques used in the thesis. 2.3.1 Lyapunov Stability The Lyapunov Stability criteria2 , ﬁrst introduced by Russian mathematician Aleksandr Mikhailovich Lyapunov (1857 − 1918), is an approach to determine the stability of an autonomous system in the form x˙ = f (x), and f (0) = 0 (2.3.1) where x = [x1 , . . . , xn ] denotes a vector containing state of the system, for example positions and velocities. Before introducing the Lyapunov stability theorems we introduce few deﬁnitions on the stability and control functions. Deﬁnition 2.3.1 (Positive/Negative Deﬁnite/Semi-Deﬁnite Functions). A continuously diﬀerentiable function W : Rn → R+ is said to be positive deﬁnite in a region U ∈ Rn that contains the origin if W (0) = 0, and W (x) > 0, ∀x ∈ U and x = 0. W (x) is said to be positive semi-deﬁnite if W (0) = 0, and W (x) ≥ 0, ∀x ∈ U and x = 0. Conversely, the function W (x) is negative deﬁnite if W (0) = 0, and W (x) < 0, ∀x ∈ U and x = 0, and negative semi-deﬁnite if W (0) = 0, and W (x) ≤ 0, ∀x ∈ U and x = 0. Stability of an Autonomous System Consider an autonomous system as in equation (2.3.1) where its stability is sought at the state x = a. For the convenience of deﬁning the stability modes, we transfer the sought state to the origin using a 2 Note that the contents (deﬁnitions and theorems) of this section is produced based on the “Stability by Lyapunov’s Direct Method With Applications” by Joseph LaSalle and Solomon Lefschetz [106]. Chapter 2. Swarm Robotics: An Introduction 17 transformation x∗ = x − a and by replacing x∗ with x, we have the general form x˙ = f (x) and f (0) = 0. Deﬁning S(R) as the spherical region x < R, H(R) as the spherical region x = R, and SrR as the closed spherical annular region deﬁned by r ≤ x ≤ R. Moreover, assume the basic existence theorem ∂fi holds for equation (2.3.1) and the partial derivatives all exist and are continuous in Ω : x < A, ∂xj where A is the radius of the sphere H(A). Let g+ be the part of g described by x(t) when t ≥ 0 and g− be the part of g described by x(t) when t ≤ 0, where g is the trajectory of x(t). Then the stability of the origin is deﬁned as follows (see Figure 2.2); Stable, whenever for each R < A there is an r ≤ R such that if a path g+ initiates at a point x0 of the spherical region S(r) then it remains in the spherical region S(R) ever after, i.e. the path starting in S(r) never reaches H(R) of S(R), Asymptotically Stable, whenever it is stable and in addition every path g+ starting inside some S(R0 ), R0 > 0, tends to the origin as time increases indeﬁnitely, and Unstable, whenever for some R and any r, no matter how small, there is always in the spherical region S(r) a point x such that the path g+ through x reaches the boundary sphere H(R). Lyapunov Stability Criteria Lyapunov stability is based on a special type of function called the Lyapunov function, which is deﬁned as follows. Deﬁnition 2.3.2 (Lyapunov function). A positive deﬁnite scalar function V (x) with the following properties; 1. V (x) is continuous together with its ﬁrst partial derivatives in a certain open region Ω about the origin 2. V (0) = 0 3. Outside the origin (and always in Ω) V (x) is positive 4. The ﬁrst partial derivative of V (x), is negative semi-deﬁnite in Ω, i.e. V˙ ≤ 0 is called a Lyapunov function. Then the Lyapunov Stability Theorems are as follows; Theorem 2.3.1 (Lyapunov Stability Theorem). If there exists in some neighborhood Ω of the origin a Lyapunov function V (x), then the origin is stable. Theorem 2.3.2 (Lyapunov Theorem for Asymptotic Stability). If there exists in some neighborhood Ω of the origin a Lyapunov function V (x) and the V˙ is negative deﬁnite, then the origin is asymptotically stable. In the essence, if one can ﬁnd (create) a function V (x) that satisfy above criteria for an autonomous system in the form described by equation (2.3.1), then the system is stable. However, this does not mean that if a particular V (x) does not satisfy the Lyapunov criteria, then the system is unstable. In many swarm robotic research studies the Lyapunov stability is used to determine the stability of a controller for convergence [39, 40, 41]. LaSalle Theorem: An Extension to the Lyapunov Criterion Extending the Lyapunov Stability criteria, LaSalle and coworkers have introduced a theorem for determining stability for systems with V˙ negative semi-deﬁnite and deﬁned as follows; 18 Chapter 2. Swarm Robotics: An Introduction Theorem 2.3.3 (Extended Lyapunov Stability Theorem ). Let V (x) be a scalar function with continuous ﬁrst partial derivatives. Let Ω1 denotes the region where V (x) < l. Assume that Ω1 is bounded and that within Ω1 : V (x) > 0 for x = 0, and V˙ (x) ≤ 0. Let R be the set of all points within Ω1 where V˙ (x) = 0, and let M be the largest invariant set in R. Then every solution x(t) in Ω1 tends to M as t → ∞. As a special case, if V˙ (x) = 0 in R only for x = 0 then the system is locally asymptotically stable at the origin. 2.3.2 Complex Integration and Winding Number Theorem In this study we are using complex domain to represent the state of the robots in 2D space in order to beneﬁt some special features of complex integration and complex analysis. This section aims in delivering the fundamental concepts behind the complex number theories used in the next two chapters. A function in complex domain is deﬁned as: a function f is a complex function whose domain Ω is a subset of complex plane and whose range is also a subset of complex plane. In other words, w = f (z) = u(z) + iv(z) is a complex function, where u(z) = u(x, y) and v(z) = v(x, y) are real-valued functions and x, y ∈ R. In complex analysis the basic form of integration is the line integral, where a function f : U → C integrated along a path γ : [a, b] → U is deﬁned as f (z)dz (2.3.2) γ where U ⊂ C or, if the contour γ is closed then the integration is represented as f (z)dz. (2.3.3) γ This can also be deﬁned, specially in numerical integration approaches, by subdividing the range [a, b] into n intervals (i.e. [a, b] = (t0 , . . . , tn ) in the form, f (z)dz ≡ γ n f (γ(tk ))γ(t ˙ k) = k=1 n f (γ(tk )) (γ(tk ) − γ(tk−1 )) (2.3.4) k=1 and the accuracy of the integral improves with n → ∞. Note that in the above expression dz = γ(t ˙ k) = γ(tk ) − γ(tk−1 ). Moreover in complex analysis, the length of a line is deﬁned as; (2.3.5) l(γ) = dz γ and can be extended to ﬁnd the circumference of a closed contour as, l(γ) = dz. (2.3.6) γ The numerical representation of the above is in the form (using similar notation as above) dz ≡ l(γ) = γ n γ(tk ) − γ(tk−1 ) (2.3.7) k=1 and since the intervals are equal (i.e. ti = γ(t1 ) − γ(t0 ) = · · · = γ(tn ) − γ(tn−1 )), we can write the above expression as, n γ(tk ) − γ(tk−1 ) = n ti (2.3.8) k=1 Chapter 2. Swarm Robotics: An Introduction 19 γ γ γ (a) Simple Closed Path (b) Open Path (c) Closed Non-Simple Path Figure 2.3: Diﬀerent Contour Types - In this study we are considering only simple close contours as the pattern generation envelope, however if one can generate non-simple contours for the pattern by combining several simple closed contours as explained in the chapter 4 Cauchy Integral Theorem and Cauchy Integral Formula We look in to some interesting results for complex integration introduced by Cauchy namely the Cauchy’s Integral Theorem and Cauchy’s Integral Formula. The Cauchy’s Integral Theorem is for a line integral along a simple-closed path (see Figure 2.3) and deﬁned as, Theorem 2.3.4 (Cauchy’s Integral Theorem). If f (z) is analytic in a simply connected domain D, then for every simple closed path C in D, f (z)dz = 0. (2.3.9) γ Theorem 2.3.5 (Cauchy’s Integral Formula). Let f (z) be analytic in a simply connected domain D. Then for any point z0 ∈ D and any simple closed path C in D that encloses z0 , f (z) dz = 2πif (z0 ). (2.3.10) γ z − z0 In this study, we use functions having a contour integral in the form, f (z)dz (2.3.11) γ and the numerical representation of such function is n f (zk ) W (z) = f (z)dz = γ (2.3.12) k=1 where zk = γ(tk ) represents a point on the path γ. For example if we use a function f (z) = z − z0 , where z0 ∈ C is a constant, then the W (z) represents the vector sum of z − z0 for all the point on the path γ (see Figure 2.4). Based on the above results of Cauchy there exists another important result on complex integration called Winding Number deﬁned as follows, Deﬁnition 2.3.3 (Winding Number). The winding number of a contour γ about a point z0 , denote by n(γ, z0 ), is deﬁned as 1 dz n(γ, z0 ) = 2πi γ z − z0 (2.3.13) which gives the number of times γ curve pases (counterclockwise) around a point. Above deﬁnition can be used to determine the position of a point (z0 ) with respect to a contour (γ) in the complex plane, i.e. if the winding number n(γ, z0 ) > 0 then the point z0 is inside the contour γ and if n(γ, z0 ) = 0 then the point lies outside the contour. We use this result in deﬁning the controller for swarm coordination in the following chapters. 20 Chapter 2. Swarm Robotics: An Introduction γ z4 z3 z2 z1 zn z0 zk Figure 2.4: Vectors Representing (zk − z0 ) 2.3.3 Perron-Frobenius Theorem The Perron-Frobenius Theorem is a theorem in matrix theory about eigenvalues and eigenvectors of a real positive n × n matrix, and it is deﬁned as follows [107, 108]; Theorem 2.3.6 (Perron-Frobenius Theorem). Let A = aij ∈ Rn×n and suppose that A is irreducible and non-negative. Then • ρ(A) > 0; • ρ(A) is an eigenvalue of A; • There is a positive vector x such that Ax = ρ(A)x; and • ρ(A) is an algebraically (and hence geometrically) simple eigenvalue of A; where ρ(A) is the spectral radius. In other words, the eigenvalue r = ρ(A) has following properties; |λ| ≤ r where λ is any other eigenvalue of A, and r can be estimated using; aij ≤ r ≤ max aij . (2.3.14) min i 2.4 j i j Problem Statements In this thesis two main problems in the swarm robotics are considered: geometric pattern generation and communication. In the geometric pattern generation problem, which is the main contribution in the thesis, we develop an artiﬁcial force based control/navigation algorithm which populates a group of robots into a pre-determined contour. In the communication problem, which acts as a supplementary work to improve the pattern generation algorithm, an all-to-all wireless communication power control algorithm is introduced such that all the members in the group can communicate with every other member instantaneously and simultaneously. Apart from that we also introduces a nodal communication power saving algorithm for mobile data collector based data collection scenario, which represents an important application of our main study. In the following section we compare our objectives with existing literature to emphasis the novel features of our architecture. 2.4.1 Geometric Pattern Generation Problem In this section we compare the proposed method for geometric pattern generation with the existing approaches. First deﬁne the problem: simply “populate a given number of robots/ agents inside a given contour”, and as secondary objectives; avoid inter-agent collisions, scalability, stability, and decentralized behavior. Chapter 2. Swarm Robotics: An Introduction 21 As described in 2.1.2, the controller we are interested is “decentralized”, and “homogeneous” such that it exclude virtual leader based approaches [65], controllers which assign speciﬁc locations for robots [64, 71] and remote information processing (for localization and navigation) techniques [63]. Moreover, we do not try to make a replica of a natural swarm [40] (such as social insects, birds etc) behavior. However the objective is to inherent the favorable aspects of such behaviors while improving the quality of ultimate goal of pattern generation. In doing so we assume a robotic system with advanced self-localization techniques and communication architecture, which could not be observed in natural swarms. The self-localization capability means that the robot is equipped with a sensing system which enable it to determine its position with respect to a global land mark. In a real robotic system this could be radar based, vision based, inertial techniques (using accelerometers) or GPS based, which could achieve the above objective. One may argue that the GPS based systems are not decentralized since it uses a global information source, however in a GPS based localization system the global source do not calculate the position of the receiver. Instead the receiver does all the calculation based on continuous data codes from three or more satellites. Thus we argue that it is decentralized as long as the processing is done at the node and the global information codes do not send speciﬁc code to each robot. Artiﬁcial force based and potential ﬁeld based approaches are extensively studied in the swarm literature. However our approach is somewhat diﬀerent from them due to dynamic calculation of the potential ﬁeld and the artiﬁcial forces. Moreover, this approach enables the robots to generate virtually any shape which can be deﬁned by a simple and closed contour (not necessarily be a mathematical expression). Under the proposed control architecture we populate a given shape (rather than the periphery as in [43, 74, 109, 85]) with the swarm without using predeﬁned positions(unlike in [64][71]) where the shapes can be described by a mathematical function (contour). The only relevant previous work which relates to this dissertation is the study by Sugihara and Suzuki in [73], in which they populate a group of agents into a simple geometric shape, i.e. circles and polygons. However, that algorithm lacks the ability of generating arbitrarily deﬁned shapes which could potentially be important in a robotic swarm deployed in a mission critical operation. The ﬁgure 2.5 compare diﬀerent formation strategies encounter in past swarm robotic literature. (a) (b) (c) (d) Figure 2.5: Diﬀerent Shape Formation Strategies - The sub ﬁgure (a) represents a scenario where the robots/agents are placed along the contour. This is particularly important in enclosing a target i.e. in escorting tasks. In the “Contour-Fill” (sub ﬁgure (b)) type formation, the area inside the target contour is ﬁlled/ populated with the robots. In the application domain this have multitude of applications such as exploration, sensor network deployment, weapon/ vehicle deployment in military applications etc, which beneﬁts the scalability and the robustness of the formation in addition to the advantages of covering an geographical area. Sub ﬁgure (c) represents a di-graph based formation strategies, which are based on graph theory based approaches. In sub ﬁgure (d) the technique used in [71] is illustrated where each robot is assigned with a speciﬁc position in the formation and the robot is navigated to occupy that place. 22 2.4.2 Chapter 2. Swarm Robotics: An Introduction Communication problem We investigate the communication problem of such a swarm of robots in which all the robots are communicating with each other at the same time[9]. Although many approaches (media and methods) can be observed for the communication, in this approach we use Radio Frequency wireless communications. Moreover, in the application-domain of the communication problem, we propose a method for powereﬃcient single-hop data collection from a randomly dispersed set of nodes where multi-hop network is not feasible[8]. As discussed in section 2.1.3, the interactive approaches based on wireless communication are not suﬃciently discussed in the swarm studies. The one-to-one communication feature in wireless sensor networks, i.e. the communication based on the node ID and the routing of information via a routing tables, makes it impractical and unsuitable for swarm robotics where the network is extremely dynamic. Moreover the node ID based communication limits the scalability and robustness of the network since the changes in node structure aﬀects the communication protocols. In our study, the above problem is eliminated by introducing a all-to-all broadcasting type wireless network which can be used in swarm robotics as well as in wireless sensor networks. Chapter 3 Geometric Pattern Generation in a Multiple Robot System This chapter introduces the main assertion of the research which lays the foundation to the rest of the thesis. The shape formation algorithm introduced here navigates a group of robots into a pre-determined shape contour and spreads them within that shape. The controller uses artiﬁcial formation forces acting on the robots, forces due to the target shape as well as due to neighboring members, which eliminate inter-member collisions and ensure smooth navigation of the group.1 First we introduce the mathematical model for the robotic system together with the artiﬁcial force functions which deﬁne the controller. Then a behavioral analysis of the group of mobile robots under the proposed controller was performed and the assertions were veriﬁed using computer simulations . In the mathematical analysis, we provide conditions for selecting the controller parameters which determines the cohesiveness, stability and the eﬀectiveness of the formation strategy. For the analysis, the following were assumed; • Agents/members have identical physical properties (such as mass, mobility etc.) • Agents/members are point masses i.e. without any physical dimensions and demonstrate point mass dynamics • Agents/members have instantaneous and error free localization capabilities • The communication network of the members can transmit data to all the members within the group instantaneously, i.e. without delay • Agents/members operate on a 2D plane without obstacles Basically the above assumptions were made in order to reduce the system complexity in the controller analysis phase and to highlight the basic formation algorithm. But in subsequent chapters of the thesis we relax these assumptions and use a swarm model which closely resembles a platoon of real world robotic vehicles. 3.1 Mathematical Model This section introduces the mathematical model of the multi-agent dynamic system together with the artiﬁcial force functions. 1 Please note that the material presented in this chapter was published as a journal paper :Ekanayake, S.W. and Pathirana, P.N., “Formations of Robotic Swarm - An Artiﬁcial Force Based Approach,” International Journal of Advanced Robotic Systems, Vol. 6, No. 1 (2009) pp. 7-24 24 Chapter 3. Geometric Pattern Generation in a Multiple ... 25 D esired TargetContour M em bers ofthe robotic group (a) Initial State (b) Final State Figure 3.1: Ultimate Objective of the Multiple Robot System - The mobile robots scatters in the space (sub ﬁgure (a)) are gathered into a clearly deﬁned contour (sub ﬁgure (b) bottom). The robots are navigated from the artiﬁcial forces which are from other robots, shape contour as well as from friction (sub ﬁgure (b) top) Remark 3.1.1. Throughout this dissertation, the terms member or agent represent a member in the swarm, while the terms swarm or multi-agent system represents the complete swarm. Also, we use C to represent complex number, R for real number and R+ to represent positive real number. Further, we use (.) and (.) to represent imaginary and real component of a complex number respectively. Remark 3.1.2. For easy representation of vector based force components with contour integrals and for ease of analysis we used the complex plane instead of the cartesian plane. But in implementing the algorithm in real robots, the cartesian vector based representations can be adopted. 3.1.1 Shape formation algorithm Consider a swarm or multi-agent system consisting of N number of identical members operating in two dimensional Euclidean space. In this context we consider the problem of controlling and positioning the above swarm into a shape bounded by a simple closed contour γ deﬁned in the complex plane, while spreading members inside the contour uniformly (see Figure 3.1). The state of the member i is described by ⎡ ⎢ Xi = ⎢ ⎣ zi ⎤ ⎥ ⎥, ⎦ (3.1.1) z˙i plane. where zi ∈ C, represents the position of the ith member in 2D complex Let zbe a point on γ, i.e. z ∈ γ. Before stating the swarm model, we deﬁne α = 1 0 and β = 0 1 . Then the state of T is determined by the continuous time dynamic model the whole swarm, x = X1 X2 X3 ... XN described by, x˙ = Ax + Bu, (3.1.2) Chapter 3. Geometric Pattern Generation in a Multiple ... Repulsive Force Magnitude Repulsive Force Magnitude Repulsive Force Magnitude 26 Y −Coordinate Y −Coordinate X −Coordinate X −Coordinate X −Coordinate Y −Coordinate (a) (b) (c) Figure 3.2: Artiﬁcial Repulsion Force Field for diﬀerent shape contours where with , A = diag Aˆ N ×N 1 ˆ B = diag B m N ×N ⎡ Aˆ = ⎣ ⎤ 0 1 ⎡ ˆ=⎣ ⎦ &B 0 0 (3.1.3) (3.1.4) ⎤ 0 ⎦. (3.1.5) 1 In (3.1.3), m is the mass of a member. According to our assumptions, notice that each member’s position information ( αX1 αX2 . . αXN ) is available to the communication network. In other words, all the members know the location matrix without a delay. The control input u in (3.1.2) consists of, T (3.1.6) u = u1 u2 u3 ... uN where ui = Fi,a + Fi,r + Fi,m − Fi,f . (3.1.7) The artiﬁcial formation forces are described as follows; Artiﬁcial Attraction Force Fi,a , attraction force on the ith member from the shape, Fi,a := ka (1 − n(γ, αXi )) (z − αXi ) dz . (3.1.8) γ Artiﬁcial Repulsion Force Fi,r , artiﬁcial repulsion force on the ith member from the shape, (αXi − z) Fi,r := kr n(γ, αXi ) 3 dz . γ αXi − z (3.1.9) In above equations, n(γ, zi ) represents the Cauchy Winding Number of γ about zi ∈ C, having the following from, 1 dz n(γ, zi ) = 2πi γ z − zi Chapter 3. Geometric Pattern Generation in a Multiple ... Remark 3.1.3. Clearly n(γ, αXi ) = 27 1 when member i is inside γ , 0 when member i is outside γ ensures that the term Fi,a in (3.1.7) vanishes only if the member is inside the contour and term Fi,r vanishes only if member is outside the shape. Collision Avoidance Force Fi,m in (3.1.7) refers to the resultant force acting on the ith member from the remaining members of the swarm (inter member repulsion force), i.e: ⎡ ⎤ N (αXi − αXj ) ⎦ . (3.1.10) Fi,m := km ⎣ αXi − αXj 3 j=1j=i Artiﬁcial Friction Force Fi,f in (3.1.7) is given by, Fi,f = kf βXi , (3.1.11) and ka , kr , km , kf ∈ R+ are the weighing parameters on the respective artiﬁcial forces. Bounds for ka , km and kf with respect to stability and cohesion of the swarm are obtained in the analysis presented in section 3.2.2. For notational simplicity, we use Fi,a , Fi,r , Fi,f and Fi,m terms instead of functionals Fi,a (xi , γ), Fi,r (xi , γ), Fi,f (xi ) and Fi,m (xi ) respectively. Fi,r and Fi,a in (3.1.7) are the artiﬁcial force ﬁelds on each member, forcing them toward the desired shape and evenly distributing them inside the contour. Fi,m term in the control function avoids the intermember collisions. The inter member interaction function looks similar to the repulsive term described in [41], [40], etc. except that the problem of decreasing repulsion behavior for small inter member distances is avoided by our repulsion term; thus preventing collision among agents. Fi,f is the artiﬁcial friction force exerted on each member, forcing the member to a complete stop when the artiﬁcial formation forces are balanced. This is to ensure that the agents reach a desirable static equilibrium state. 3.1.2 Simulation results In the following simulation ﬁgures, the shape contour is generated using the function described in the Appendix I. Artiﬁcial forces In this section the behavior of artiﬁcial forces are illustrated. In ﬁgure 3.3, the motion of a single robot under the proposed controller is simulated. To clearly visualize the behavior of the artiﬁcial forces, the member is kept on the X-axis (real axis) of the coordinate system while the center of the contour was placed on the (0,0) coordinate; resulting the robot to move along the real-axis. Here, the artiﬁcial forces Fi,a , Fi,r and Fi,f were plotted with the distance traveled along the real-axis in sub ﬁgures (a),(b) and (c) respectively while the motion of the robot is shown in the sub ﬁgure (a). For this simulation the following parameters were used: a = 5, b = 1, c = 0.7, d = 60, ka = 0.004, kr = 4000, km = 60000, kf = 9 The ﬁgure 3.4 demonstrates the motion of four robot under the proposed controller and the behavior of the artiﬁcial forces. In the ﬁgure 3.4.(a), motion paths of the all four members were plotted. The behavior of the resultant force and the speed of the robots are shown in ﬁgures 3.4.(b) and (c) respectively, which gives an idea on the stable state of the robots. According to the simulation ﬁgures, the robots reach a stable state by the 450th time step where the total force acting on each member and their speeds reach zero. In the ﬁgure 3.5 the behavior of artiﬁcial forces were illustrated for the above case. The following 28 Chapter 3. Geometric Pattern Generation in a Multiple ... 400 Magnitude x 10 N Angle / (deg) Target contour Force Magnitude/Angle Y−Coordinate [m] 300 200 Path of motion 100 0 −100 −200 300 200 100 0 −100 −300 −600 −400 −200 0 −200 −600 200 X−Coordinate [m] −500 −400 −300 −200 −100 0 Travel in X direction [m] (b) Behavior of the Fi,a force (a) Path of motion 300 300 200 200 Force Magnitude/Angle Force Magnitude/Angle Magnitude x 10 N Angle / (deg) 100 100 0 −100 0 −100 −200 −600 −500 −400 −300 −200 −100 Travel in X direction [m] (c) Behavior of the Fi,r force 0 Magnitude x 10 N Angle / (deg) −200 −600 −500 −400 −300 −200 −100 0 Travel in X direction [m] (d) Behavior of the Fi,f force Figure 3.3: Behavior of artiﬁcial forces for a single robot simulation parameters were used to generate the ﬁgures 3.4 and 3.5: a = 5, b = 1, c = 0.7, d = 60, ka = 0.004, kr = 4000, km = 60000, kf = 9. Motion of the entire swarm The simulation case studies presented in this section demonstrates the behavior of the shape formation algorithm in diﬀerent scenarios representing diﬀerent group sizes and initial states of the swarm (Figures 3.8 and 3.9), and behavior of the swarm when subjected to disturbances, i.e. removal of members (Figure 3.10), addition of members (Figure 3.11) and changes in the shape (Figure 3.12). 3.2 Behavior Analysis Total force acting on an individual member makes it travel toward the shape when it is outside the shape and will converge toward a stable position when it is inside the shape. As the formation force components (Fi,r and Fi,a ) do not act simultaneously, we can analyze the behavior and the stability of the controller in each instance separately. In section 3.2.2, we ﬁrst analyse the behavior of the complete swarm when all the members are outside the shape, i.e. when every member is subjected to Fi,a force. Next, we analyse the behavior of a member staying outside the shape, with claims on the direction of motion. With analysis of the behavior of a single member inside the shape contour, in section 3.2.3, we provide equilibrium position(s) inside a shape contour symmetrical over two or more axes. Then we discuss the results with logical explanations on the swarm behavior in speciﬁc situations (section 3.2.4). Before analysing the Chapter 3. Geometric Pattern Generation in a Multiple ... 29 behavior of the swarm, we deﬁne the following; N zcm = (zi ) z dz i=1 zc = N γ dz , l(γ) = l(γ) (3.2.1) γ where zcm , zc and l(γ) represent the center of mass of the swarm, the center of mass of the contour and length of the contour respectively. 3.2.1 X Swarm deﬁnition A swarm S is deﬁned as “X swarm”, if there exists positive constants Δ, δ that satisfy the following conditions simultaneously for all i, j ∈ S and i = j. 1. dij ≥ δ + Δ, i zi − zcm Δ 3 , < 1+ 2. zi − zcm δ 300 Robot 2 path 200 Robot 1 path Y−Coordinate [m] 100 0 −100 −200 −300 Robot 4 path −400 Robot 3 path −500 −600 −600 −400 −200 0 200 400 600 X−Coordinate [m] (a) Path of motion: Initial positions of the robots are shown in crosses and the ﬁnal positions are indicated in dots 350 8 Force Magnitude 250 200 150 100 50 Robot 1 Robot 2 Robot 3 Robot 4 6 Force Magnitude Robot 1 Robot 2 Robot 3 Robot 4 300 4 2 0 0 −50 0 100 200 300 400 500 Time Step (b) Behavior of the FR (Resultant) force −2 0 100 200 300 400 500 Time Step (c) Variation of the speed of robots Figure 3.4: Behavior of artiﬁcial forces 30 Chapter 3. Geometric Pattern Generation in a Multiple ... 350 350 Force Magnitude 250 200 150 100 50 Robot 1 Robot 2 Robot 3 Robot 4 300 Force Magnitude Robot 1 Robot 2 Robot 3 Robot 4 300 0 250 200 150 100 50 0 −50 0 100 200 300 400 −50 0 500 100 Time Step 300 400 500 Time Step (a) Behavior of the Fi,a force (b) Behavior of the Fi,r force 350 350 250 200 150 100 50 0 Robot 1 Robot 2 Robot 3 Robot 4 300 Force Magnitude Robot 1 Robot 2 Robot 3 Robot 4 300 Force Magnitude 200 250 200 150 100 50 0 −50 0 100 200 300 400 500 −50 0 100 Time Step 200 300 400 500 Time Step (c) Behavior of the Fi,f force (d) Behavior of the Fi,m force Figure 3.5: Behavior of artiﬁcial forces in diﬀerent orientations where N i = dij = zi − zj and zcm zj j=1;j=i N −1 . i is the center of mass of the swarm without the ith member. In the above deﬁnition, zcm In the ﬁrst condition of the “X Swarm” deﬁnition, we impose a constraint on the distance between robots in a group. That is the distance di,j is larger than a selected value (δ+Δ). From the second condition we set the ratio between δ and Δ, in which the ratio can be made to move toward zero with the increasing size of the swarm. Using the deﬁnition of “X Swarm” we derive that the inter member repulsion force (Fi,m ) on any member of the swarm is bounded, as presented in following lemma. Lemma 3.2.1. For a member of a “X Swarm”, the magnitude of the artiﬁcial inter-member repulsion km (N − 1) zi − zcm , force is less than δ3 Proof. N (zi − zj ) . (3.2.2) Fi,m = km d3ij j=1,j=i Using the condition 1 of the “X Swarm”, we have Fi,m < km (N − 1) i zi − zcm ). (δ + Δ)3 (3.2.3) 500 400 400 300 300 300 200 100 0 200 100 0 −100 −200 −300 Y−Coordinate [m] 500 400 −100 −200 −500 −400 −300 −200 −100 0 100 200 300 −300 400 200 100 0 −100 −200 −500 −400 −300 −200 −100 X−Coordinate [m] 0 100 200 300 −300 400 (b) T=50 400 300 300 300 0 Y−Coordinate [m] 500 400 Y−Coordinate [m] 500 100 200 100 0 −200 −200 −200 −300 −300 200 300 400 −500 −400 −300 −200 −100 0 100 200 300 400 −300 −500 −400 −300 −200 −100 X−Coordinate [m] (d) T=150 400 200 300 400 0 −100 100 300 100 −100 0 200 200 −100 X−Coordinate [m] 100 (c) T=100 400 200 0 X−Coordinate [m] 500 −500 −400 −300 −200 −100 −500 −400 −300 −200 −100 X−Coordinate [m] (a) T=0 Y−Coordinate [m] 31 500 Y−Coordinate [m] Y−Coordinate [m] Chapter 3. Geometric Pattern Generation in a Multiple ... 0 100 X−Coordinate [m] (e) T=200 (f) T=150 Figure 3.6: Motion sequence representation using snap shots - The sub ﬁgures (a) to (f) shows the motion sequence of the swarm as snap shots and the same motion is represented as continuous motion paths in the Figure 3.7 500 400 Y−Coordinate [m] 300 200 100 0 −100 −200 −300 −500 0 500 X−Coordinate [m] Figure 3.7: Motion sequence representation using motion paths - The motion of the entire swarm is represented as motion paths, here the initial positions are represented by “X” signs, ﬁnal positions as “O” signs and the paths of motion as lines. Then using the condition 2, the following can be derived; Fi,m < km (N − 1) zi − zcm . δ3 (3.2.4) 32 Chapter 3. Geometric Pattern Generation in a Multiple ... 200 0 200 −200 Y−Coordinate [m] Y−Coordinate [m] −400 −600 −800 −1000 −1200 100 0 −100 −200 −1400 −1600 −300 −1800 −400 −500 0 500 1000 1500 −300 −200 −100 0 100 200 300 400 500 X−Coordinate [m] 2000 X−Coordinate [m] (a) Robots far away from the target contour (b) Closeup view of the robots populated inside the shape 500 1500 400 300 Y−Coordinate [m] Y−Coordinate [m] 1000 500 0 −500 200 100 0 −100 −200 −300 −1000 −400 −1500 −2000 −1500 −1000 −500 0 500 1000 1500 −500 −600 2000 −400 X−Coordinate [m] −200 0 200 400 600 X−Coordinate [m] (c) Robots far away from the target contour (d) Closeup view of the robots populated inside the shape Figure 3.8: Formation into a shape, starting from diﬀerent state vectors. Following parameters were used for the simulation case studies: a = 5, b = 1, c = 0.7, d = 60, ka = 0.004, kr = 4000, km = 60000, kf = 9 300 400 300 200 Y−Coordinate [m] Y−Coordinate [m] 200 100 0 −100 100 0 −100 −200 −300 −200 −400 −500 0 500 X−Coordinate [m] (a) All the robots are outside the contour at the initialization −300 −300 −200 −100 0 100 200 300 X−Coordinate [m] (b) Some robots are inside the target contour at the initialization Figure 3.9: Formation with robots starting closer to the contour. Following parameters were used for the simulation case studies: a = 5, b = 1, c = 0.7, d = 60, ka = 0.004, kr = 4000, km = 60000, kf = 9. The above result is an upper bound for the magnitude of the inter member repulsion force Fi,m in a “X swarm”, which we use in the proceeding sections. −2000 −2000 −2100 −2100 Y−Coordinate [m] Y−Coordinate [m] Chapter 3. Geometric Pattern Generation in a Multiple ... −2200 −2300 −2400 −2500 33 −2200 −2300 −2400 −2500 −2600 −2600 600 700 800 900 1000 1100 1200 1300 600 700 X−Coordinate [m] 800 900 1000 1100 1200 1300 X−Coordinate [m] (a) Initial situation (b) Motion of the robots to include new members Figure 3.10: Behavior of the robots when new members are assigned to the swarm - - the ﬁnal positions are represented by the dots and the motion paths are represented by lines. The shape contour used in this case is deﬁned by the parameters: a = 5, b = 1, c = 0.7, d = 60, and the controller used the following weighing parameters: a = 5, b = 1, c = 0.7, d = 60. −2000 −2100 Removed members −2200 −2300 −2400 −2500 −2600 700 Y−Coordinate [m] Y−Coordinate [m] −2000 −2100 −2200 −2300 −2400 −2500 800 900 1000 1100 1200 1300 1400 −2600 700 800 900 X−Coordinate [m] (a) Initial situation 1000 1100 1200 1300 1400 X−Coordinate [m] (b) Redistribution of the robots after the loss Figure 3.11: Behavior of the robots when member assigned to the swarm are lost or removed - the ﬁnal positions are represented by the dots and the motion paths are represented by lines. The shape contour used in this case is deﬁned by the parameters: a = 5, b = 1, c = 0.7, d = 60, and the controller used the following weighing parameters: a = 5, b = 1, c = 0.7, d = 60. 3.2.2 Cohesiveness Swarm and Members Outside the Shape Firstly, we examine the behavior of the swarm, when all the members are outside the contour. In our analysis, the swarm is considered as one object in which the motion is governed by the resultant artiﬁcial force (R), (3.2.5) R = Ra − Rf + Rm . With this, the equation of motion of the whole swarm can be described by, m ε¨ + kf ε˙ + ka l(γ) ε = 0. where ε = (zcm − zc ), with ε˙ = z˙cm , ε¨ = z¨cm . (3.2.6) Chapter 3. Geometric Pattern Generation in a Multiple ... −2000 −2000 −2100 −2100 Y−Coordinate [m] Y−Coordinate [m] 34 −2200 −2300 −2400 −2500 −2200 −2300 −2400 −2500 −2600 −2600 700 800 900 1000 1100 1200 1300 1400 700 800 X−Coordinate [m] 900 1000 1100 1200 1300 1400 X−Coordinate [m] (a) Initial situation (b) Motion of the swarm Figure 3.12: Behavior of the swarm when the shape contour suddenly changed. In the simulation the initial formation is on a shape deﬁned by the parameters a = 5, b = 1, c = 0.7, d = 60 and then the shape suddenly changed into the shape deﬁned by the parameters a = 5, b = 1, c = 0.7, d = 60. The simulation ﬁgures demonstrates the motion of the swarm to re-organize into the new shape. Notice that in (3.2.5); Rm , which represents the resultant inter member force is zero as, Rm = N N i=1 j=1j=i (αXi − αXj ) = 0. αXi − αXj 3 Ra , the resultant artiﬁcial attraction force from the contour, is expressed as, N (z − αXi ) dz , Ra = ka i=1 γ and using deﬁnitions for zc , zcm and l(γ), the above can be stated as: Ra = l(γ)N ka (zc − zcm ) . Rf , represents the resultant artiﬁcial damping (friction) force, and is in the form of, Rf = N kf (z˙cm ) . Therefore, the net resultant force on the swarm (this force is applied on the center of mass of the swarm) is, R = N l(γ)ka (zc − zcm ) − N kf (z˙cm ) , and hence the motion dynamics of the swarm can be described by (3.2.6). With the above motion dynamics of the whole swarm, we obtain our ﬁrst result; the center of mass of the swarm (zcm ) moves toward the shape (see Figure 3.13). This is given in the form of the following Proposition. Proposition 3.2.2. Consider the swarm model described by (3.2.6), motion of the center of mass of the swarm (zcm ) is in the direction of decreasing ε (i.e. toward the center of mass of the contour zc ). 1 1 Proof. If we select a Lyapunov function candidate as Vcm = mε˙ε˙T + ka l(γ)εεT , then the derivative 2 2 V˙ cm is bounded by, ˙ 2. V˙ cm ≤ −kf ε ˙ = 0, the only invariant point is the origin (i.e. ε = ε˙ = 0), thus using extended ˙ 2 > 0, ∀ε Since kf ε version of Lyapunov’s method proposed by LaSalle and Lefschetz (Theorems VI and VII in [106]) we can state that the system is asymptotically stable at the origin, which proves our assertion. Chapter 3. Geometric Pattern Generation in a Multiple ... 35 400 300 300 Y−Coordinate [m] Y−Coordinate [m] Zoom in Area 400 200 100 0 200 100 0 −100 −100 −200 −200 −300 −500 −400 −300 −200 −100 0 100 200 300 −300 400 −500 −400 −300 X−Coordinate [m] −200 −100 0 100 200 300 400 X−Coordinate [m] (a) Simulation upto T=75 - All the members are outside the target contour (b) Simulation upto T=147 - Some of the members moved into the target contour 260 Y−Coordinate [m] 240 220 200 180 160 140 −260 −240 −220 −200 −180 −160 −140 −120 X−Coordinate [m] (c) Zoom in view of the sub figure (b), showing the deviation from the straight line motion. Figure 3.13: Motion of the center of mass of the swarm zcm is toward the center of the contour zc . In the ﬁgure zcm is represented by the red colors while the motion of individual members are represented by blue color. Note that the motion of the center is along a straight line connecting the starting position of it (zcm (0)) and zc (dashed red line). Also note that, after the members move inside the shape, the zcm does not move along the projected path. Basically, this Proposition says that the motion of the center of mass of the complete swarm is toward the center of mass of the contour and this holds, regardless of the motions of members with respect to zcm . Note that Proposition 3.2.2 does not hold, if any member of the swarm moves into the shape. Remark 3.2.1. Using the properties of second order ODEs one can state that; smooth motion of the swarm (i.e. damped motion dynamics) toward the target contour (zc ) can be obtained if the conditions m, ka , kf > 0 and kf ≥ 2 m ka l(γ) are satisﬁed (see Figure 3.14). Proposition 3.2.2 shows only the behavior of the swarm, but it does not say anything about the behavior of an individual agent. Next we investigate the behavior of the members in a speciﬁc swarm, where the members have a predeﬁned minimum spacing: “X Swarm”. Further, we introduce a condition for a “X Swarm” to be cohesive under Fi,a force in the Proposition to follow. Members Outside the Shape Before investigating more into the behavior of a single member, we deﬁne the error between zi and zcm as υi = (zi − zcm ); resulting υ˙ i = (z˙i − z˙cm ) and υ¨i = (¨ zi − z¨cm ). From the swarm model introduced in (3.1.2), the motion of any member outside the contour can be described by, 36 Chapter 3. Geometric Pattern Generation in a Multiple ... 500 400 400 300 200 Y−Coordinate [m] Y−Coordinate [m] 300 200 100 0 100 0 −100 −100 −200 −200 −300 −500 −400 −300 −200 −100 0 100 200 300 400 −300 −400 −300 X−Coordinate [m] −100 0 100 200 300 400 X−Coordinate [m] m k (a) kf = 0.65 × 2 m k l(γ) a (b) kf = 1 × 2 400 350 300 300 a l(γ) Over damped (Figure (c)) Critically damped (Figure (b)) Under damped (Figure (a)) 250 200 Y−Coordinate [m] −200 200 100 150 0 100 −100 50 −200 0 −300 −50 −400 −300 −200 −100 0 100 200 300 400 0 50 100 150 200 X−Coordinate [m] m k (c) kf = 1.5 × 2 a l(γ) (d) zcm − zc Figure 3.14: Second order motion dynamics of the swarm - kf > 2 m ka l(γ) indicates a stable aggregation of the members (sub ﬁgure (c)), when the entire group is outside the shape. Diﬀerent values for kf generates diﬀerentswarm behaviors, kf < 2 m ka l(γ) generate under-damped motion dynamics (sub ﬁgure (a)), kf = 2 m ka l(γ) generates critically damped motion dynamics (sub ﬁgure (b)) and the sub ﬁgure (d) shows the motion of the center of mass of the swarm ( = zcm − zc ) for all of above cases. Note that each case is simulated for 200 steps, starting from the same initial position vector and with simulation parameters; a = 3, b = 1, c = 0.7, d = 1, ka = 1, kr = 4000, km = 60000. 1 ka × l(γ)(zc − zi ) + km z¨i = m in which we used, N (zi − zj ) − kf z˙i zi − zj 3 j=1,j=i (3.2.7) Fi,a = ka γ (z − αXi ) dz = ka × l(γ) (zc − zi ) , (3.2.8) as n(γ, αXi ) = 0. From (3.2.6) and (3.2.7), m υ¨ + kf υ˙ + ka l(γ) υ − km N (zi − zj ) = 0, zi − zj 3 j=1,j=i (3.2.9) which describes the motion of a single agent with respect to the center of mass of the swarm. In the following Proposition we introduce a condition for a “X Swarm” to be cohesive under Fi,a with a member having motion dynamics given by (3.2.9). Also with this condition we can describe the direction of motion of any member of a “X Swarm” outside the shape. Chapter 3. Geometric Pattern Generation in a Multiple ... 37 Proposition 3.2.3. Consider a member i of a “X Swarm” staying outside the desired shape at any given (N − 1) ka , then the motion of that member is in the direction of decreasing υ (i.e. toward > 3 time, if km δ × l(γ) the center of the swarm zcm ). Proof. Choosing a Lyapunov function candidate for the member i as 1 1 km (N − 1) T T Vi = mυ˙ i υ˙ i + υi υi ka l(γ) − 2 2 δ3 and taking derivatives, we can show that V˙ i is bounded by, ⎛ ⎞ N (zi − zj ) km (N − 1) ˙ 2 + ⎝ υ⎠ υ. ˙ V˙ i ≤ −kf υ km 3 − δ3 j=1,j=i zi − zj Since we consider a member of a “X Swarm”, from Lemma 3.2.1, N (zi − zj ) (N − 1) zi − zcm 3 < δ3 j=1,j=i zi − zj and hence, V˙i < −kf υ˙i 2 (3.2.10) (3.2.11) (3.2.12) (3.2.13) which proves the assertion. This Proposition describes the motion of a robot which is a member of a “X Swarm” and staying outside the shape. To satisfy the above conditions, there is no restriction on the positions of the other members of the swarm or the position of zcm , i.e. they may either be inside or outside the target shape. Remark 3.2.2. Consider a group of robots released far away from the desired shape, having an artiﬁcial force based controller described in (3.1.7) and satisfying “X Swarm” hypothesis. In general terms Propositions 3.2.2 and 3.2.3 infer that the robots (members) move toward the shape. Simulation of “X Swarm” Behavior In this section we demonstrate the validity of the “X Swarm” hypothesis in a simulated swarm, evaluating our results presented in Propositions 3.2.2 and 3.2.3, i.e. motion of the center of mass of the swarm and the motion of an individual outside the swarm. Proposition 3.2.2 does not impose any restriction for convergence other than the selection of kf for stability. According to Proposition 3.2.3, for a member (N − 1) ka has a motion towards the > 3 of a “X Swarm”, staying outside the shape while satisfying km δ × l(γ) center of mass of the swarm. Thus we have δ > 80m to satisfy the above condition, and Δ is selected as 2m. We select the initial positions with members spaced more than δ + Δ and simulate the motion for 100s in which the swarm motion is shown in Figure 3.15.(a). Observing the ﬁgure 3.15.(b) center error (), which is the error between center of mass of the swarm (zcm ) and the center of mass of the contour (zc ), continuously decrease even after the members are inside the shape. Note that the center error rapidly decrease while the members are outside the shape, demonstrating the behavior predicted by Proposition 3.2.2 and after moving into the shape we can observe a slow convergence. Figures 3.15.(d) and (c) illustrate the behavior of member error (υ) for three selected members and the average error. We have intentionally chosen the parameters such that “X Swarm” behavior is achieved only for a certain period. The regions “A” and “B” represents the time spans where “X Swarm” hypothesis is valid. Note that since the swarm expands after it reaches the shape, the “X Swarm” hypothesis is valid for all t > 100. In the zoomed view of the member error (Figure 3.15.(d)), one can notice that the members converge 38 Chapter 3. Geometric Pattern Generation in a Multiple ... 1000 2500 Initial positions @t=0 0 −500 −1000 Final positions inside the shape @t=100 −1500 −2000 −2500 −2000 First member enters the shape @t=7 2000 Center Error (ε) [m] Y−Coordinate [m] 500 −1000 0 1000 1500 1000 500 0 0 2000 20 (a) Motion of the complete swarm 1200 A 300 B 80 100 A 250 Member Error (υ) [m] Member Error (υ) [m] 60 (b) Center Error 1000 800 600 400 200 0 0 40 Time [s] X−Coordinate [m] 20 40 60 80 100 200 150 100 50 0 0 5 10 15 20 Time [s] Time [s] (c) Member error and “X Swarm” regions (d) Member error (zoomed view) 25 Figure 3.15: Swarm motion and “X Swarm” hypothesis, for (δ + Δ) > 82m and N = 14. In ﬁgures (c) & (d), the regions “A” and “B” represents the regions where “X Swarm” conditions are satisﬁed. The dots represents the instance when that member enters the shape and the red line represents the average member error. Following simulation parameters were used in this simulation; a = 5, b = 1, c = 0.5, d = 80, ka = 7 × 10−3 , kr = 5 × 103 , km = 6 × 106 . toward the center of mass of the swarm despite the invalidity of the “X Swarm” hypothesis and even after the member enters the shape. Also from the ﬁgures it can be noticed that member error continuously decreases when the member is outside the shape and the swarm behaves as a “X Swarm”, demonstrating the validity of the assertions presented in Proposition 3.2.3. 3.2.3 Comment on stable locations inside the shape So far we have analyzed the behavior of the swarm and individual members staying outside the contour. In this section we investigate the behavior of Fi,r formation force acting on an agent, where the contour γ is symmetrical over one or more straight lines. Then we comment on the stable location of the swarm. In the following lemma, we use odd and even function properties to derive a property of a complex function which is symmetrical over real axis of the complex plane. Lemma 3.2.4. For a closed contour γ(θ) and functionals f1 (θ) ∈ R+ , f2 (θ) ∈ C for θ ∈ [0, 2π], with the following properties, γ(θ) = γ ∗ (2π − θ), f1 (θ) = f1 (2π − θ), f2 (θ) = γ(θ) − CR , CR ∈ R, Chapter 3. Geometric Pattern Generation in a Multiple ... 39 2 1 3 (a) Collection of symmetrical shapes (b) Non symmetrical shape Figure 3.16: A non-symmetrical shape as a collection of symmetrical shapes. Any 2D shape can be generated (approximately) using several symmetrical shapes. The analysis for symmetrical shapes can easily be extended to non symmetric shapes, considering them as a collection of symmetric shapes and the robot sub groups are assigned to each symmetrical shape. the following statement holds, 2π f1 (θ)f2 (θ)dθ 0 Proof. Let P1 = as f1 (θ) ∈ R+ P1 = 2π 0 =0 f1 (θ)f2 (θ)dθ , (3.2.14) 2π 0 f1 (θ) (f2 (θ)) dθ. (3.2.15) Since f1 (θ) and (f2 (θ)) are even and odd around θ = π respectively, P1 = 0, (3.2.16) Before stating our result about a member, we discuss the nature of the artiﬁcial formation force, Fi,r (zi − z) (zi − z) deﬁning the direction in detail. Fi,r = kr dz consists of two major components, 3 z − z z i i − z γ 1 determining the magnitude of the force. The expression for Fi,r is of the force component and zi − z2 the contour integral representation of K (zi − zk ) where zk ∈ γ zi − zk 3 (3.2.17) zk − zk−1 = zk+1 − zk , ∀k; when K → ∞ (3.2.18) k=1 and In our analysis we deﬁne, 1 . zi − z3 Using polar coordinate representation for complex plane, we reformulate Fi,r as 2π f (γ(θ), zi ) (zi − γ(θ)) γ(θ) ˙ dθ Fi,r = kr f (z, zi ) = 0 which is used to prove our next results. (3.2.19) (3.2.20) 40 Chapter 3. Geometric Pattern Generation in a Multiple ... −1200 −1300 Y−Coordinate [m] Y−Coordinate [m] −1350 −1400 −1450 −1500 −1550 −1600 −1300 −1400 −1500 −1600 −1700 −1650 −1700 −1800 800 900 1000 1100 1200 1300 600 700 X−Coordinate [m] 800 900 1000 1100 1200 1300 1400 X−Coordinate [m] (a) Motion of a single agent under Fi,r force. (b) Motion of the whole swarm inside the contour. Figure 3.17: Motion of members under Fi,r force. Dotted lines represent symmetrical axes of the shape. In (b), the motion of the center of mass of the weapons is represented in black while red lines represent the motion path of individual members. The initial and ﬁnal positions are represented by a cross and a dot respectively. Proposition 3.2.5. Consider a member i inside a given contour γ(θ) with the following properties: 1. γ(θ) = γ ∗ (2π − θ), 2. (zi ) = 0. Then, (Fi,r ) = 0. (3.2.21) Proof. Fi,r in equation (3.2.20), have the following properties when (zi ) = 0, ˙ = f (γ(2π − θ), zi )γ(2π ˙ − θ) f (γ(θ), zi )γ(θ) (3.2.22) (zi − γ(θ)) = −(γ(θ) − zR ), zR ∈ R (3.2.23) (Fi,r ) = 0. (3.2.24) thus using Lemma 3.2.4, Above result say that for any member i staying on the real-axis and inside the shape, which is symmetrical around the real-axis, the component of Fi,r parallel to the imaginary axis is zero. In other words, the Fi,r force on that member is along the real axis. Further we extend the above result to a shape with an axis of symmetry other than the real-axis and then prove that the equilibrium point lies on the intersection of the symmetric axes, as shown in the following Proposition. Proposition 3.2.6. Consider a given contour γ(θ) = r(θ)eiθ with two symmetric axes. Then, for a member i staying on the intersection of the symmetrical axes, the artiﬁcial repulsion force from the contour (Fi,r ) is zero. Proof. Consider two symmetric axes(k, l) form αk , αl ∈ [0, 2π] angles to the real axis. Assume the member is on the intersection of the symmetric axes. Then, from Proposition 3.2.5, Fi,r is in the form of : Fi,r = μk eiαk = μl eiαl where μk , μl ∈ R. As αk = αl , this implies μk = μl = 0. Thus Fi,r = 0. (3.2.25) Chapter 3. Geometric Pattern Generation in a Multiple ... 41 Above result states that, for a contour symmetrical over two intersecting straight lines, there exists a point, where Fi,r = 0. In other words, the intersection point of symmetric axes is a possible equilibrium point for the member moving under Fi,r artiﬁcial formation force. Our computer simulations conﬁrm these assertions. (refer Figure 3.17.(a)) Remark 3.2.3. The analysis of the motion of a single member can be extended to determine the behavior of the complete swarm (when all agents are inside the shape). By considering the complete swarm as one object with the center of mass of the swarm being the center of the object, we can conclude that the swarm will have a stable equilibrium under Fi,r force, with the center of mass of the swarm moved to the center of mass of the contour which is symmetrical over a minimum of two intersecting straight lines(see Figure 3.17.(b)). 3.2.4 Discussion on Analysis In the previous sections the behavior of the swarm and individual members were analysed for the following cases (the summarized results are given below); (i). Center of mass of the swarm (zcm ) : If all the members are outside the shape, the motion of the center of mass of the swarm (zcm ) is towards the center of mass of the contour (zc ). (ii). A member outside the shape : With the “X Swarm” assumptions and conditions on Proposition 3.2.3 remain true, the motion of an individual will be towards the center of mass of the swarm. (iii). Inside a symmetrical shape : (a). A member will have a stable equilibrium point on the symmetrical axis. Further, if the shape has two or more intersecting axes, then the stable equilibrium point lies on the intersection of the axes. (b). When all the members are inside the shape, then the motion of the center of mass of the swarm (zcm ) will have a stable equilibrium point on the symmetrical axis. As in the previous case, this stable equilibrium point lies on the intersection of the symmetrical axes.. Next we focus our attention to the aspects which were not considered in the mathematical analysis provided in the previous sections. When a section of the swarm is inside the contour we can use Proposition 3.2.3 to describe the motion of a member outside the contour, provided that the swarm behaves as “X (N − 1) ka means that, the inter-member > 3 Swarm”. A swarm which does not satisfy the condition; km δ × l(γ) repulsion term is dominating than the attraction towards the center of mass of the swarm. Thus members are more likely to have diverging behavior until the “X Swarm” conditions are satisﬁed. This behavior is basically to avoid inter-member collisions and by changing the parameters ka , km and δ the cohesiveness of the swarm can be improved. A major drawback of the controller is the discontinuous nature of the artiﬁcial formation forces (i.e. Fi,r and Fi,m ), which may cause chattering eﬀect at the boundary of the shape. Since the term n(γ, αXi ) is not deﬁned on the contour, the member will continue its motion using the previous motion dynamics until it passes the boundary. Since the boundary is a line without a thickness, this problem will not be a signiﬁcant unless a member is on the boundary at the beginning. However, the inter member forces acting on such members does not allow them to stay on the contour once the algorithm is initialized. Also, as shown in the ﬁgure 4.4, the formation forces (Fi,a and Fi,r ) which drives the members into the contour has a signiﬁcant variation at the boundary. Specially the decreasing magnitude of the driving force when a member is staying closer but outside of the contour, may result in the member to staying outside the contour at the equilibrium state. This happens only when the contour is not large enough to accommodate all the members, thus Fi,m becomes larger than Fi,a such that some members are not allowed in. This problem can be eliminated by carefully selecting ka and km parameters which suit the application and the swarm size. 42 Chapter 3. Geometric Pattern Generation in a Multiple ... 3.3 Summary In this chapter, we introduced the basic swarm model together with the artiﬁcial force based controller. The controller navigates a group of robots in a decentralized manner to populate a given contour. Properties of the robotics swarm, i.e. robustness, ﬂexibility and scalability, are presented in the form of simulation case studies. Moreover, the analytical results derived for the controller for the stability and other behaviors were evaluated using simulation case studies. The criteria for selecting weighing parameters can be summarized as follows; • For damped motion (smooth motion) of the entire swarm kf ≥ 2 m ka l(γ). • For cohesive behavior of the swarm (N − 1) ka . > 3 km δ × l(γ) Chapter 4 Application Case Study: Swarming Guided Weapons This chapter uses the main result of the pattern generation algorithm and modify it to suit a speciﬁc application “Airborne Swarming Guided Robot / Weapon System” which has many potential applications ranging from military to humanitarian. The concept was initially developed for an airborne guided weapon system which acts as an alternative to cluster weapons1 . 4.1 Motivation and Background Neutralizing a wide-spread target in a single attack is one of the primary aims in any military operation. Using weapons with increased lethal radii and deploying multiple weapons over the target area are the commonly practiced approaches against wide-spread targets. In the former approach the destructive power does not evenly distribute over the target area. Instead it delivers the highest power at the point of impact and the destructive power decrease along the radii. Further, the uncontrolled nature of destruction in weapons with higher lethal radii causes increased collateral damage and civilian causalities (e.g. Nuclear weapons deployed at Hiroshima and Nagasaki during WWII caused unaccounted civilian causalities [110]). In multiple weapon deployment approaches, MLRS (Multiple Launch Rocket Systems) have become the weapon of choice against short range targets (typically less than 50km) while air raids are used against long distance targets. In most wide spread targets such as military establishments, air ﬁeld complexes, armored vehicle/military personnel gatherings etc, it is highly unlikely to locate speciﬁc targets for long range guided weapons, specially with moving targets in adverse weather conditions where satellite intelligence become ineﬀective. This create the need to employ air launched unguided or visual range guided weapons (Laser Guided, Video Guided etc) against such targets. In such close combat air raids, air crafts are highly vulnerable to hostile attacks resulting in loss of lives of talented pilots and expensive aircrafts. In this chapter we introduce a novel approach to deploy multiple weapons against a widespread target. Typically in most wide-spread targets, a clear geographical boundary that distinguishes the target from the surrounding environment can be identiﬁed. Here we use the geographically bounded nature of widespread targets to ensure all the weapons lie inside the target boundary at the time of impact causing maximum destruction at the target while minimizing the problem of collateral damage. Also in the proposed controller, weapons are evenly distributed inside the desired geographical area causing uniform destruction to the target while using the ammunitions eﬀectively. In our approach, the weapons are not necessarily launched by a single deployment system. Instead it controls the guided weapons launched by air craft(s) or MLRS as a group in the swarm aggregation and shape formation algorithm. 1 Please note that the material presented in this chapter is based on: Samitha W Ekanayake and Pubudu N Pathirana,“Two Stage Architecture for Navigating Multiple Guided Weapons into a Widespread Target”, in IEEE Aerospace conference 2008, Big Sky, Montana, USA 43 44 Chapter 4. Application Case Study: Swarming Guided Weapons Guided weapons started service in WWII, and since then the automatic navigation of weapons and aircrafts have became a top priority research theme for most research scientists and organizations. Based on methods, navigation and guidance of weapons can be categorized into four main groups, inertial navigation, command guidance, homing guidance and beam riding [111]. Among them, inertial navigation is the only system that relies on internal programming and control, while the other three depend on external sources of sensing and control. Since the V2 rocket, the ﬁrst successful inertial guided weapon developed by Germans in WWII [111], the Inertial Navigation Systems (INS) gain rapid developments assisted by advances in electronics [112]. With the introduction of GPS technology [113] and less than 5m positional accuracy on P-Code GPS receivers, new frontiers in navigational systems research [114, 115, 116, 117, 118] have opened up. Integrated GPS/INS guiding system have been preferred as opposed to GPS only systems due to the presence of jammers in electronic warfare [119]. The combined system enhances long range accuracy in INS and achieves improved navigation of weapons even when GPS coverage is not available [120, 121, 122, 123, 124, 125]. In the proposed scheme, weapons are equipped with GPS/INS navigation system (e.g. JDAM), where navigation does not depend on external sensors. As in JDAM controlled weapons, the system has to be pre-programmed for the ﬁnal destination and group parameters. Initial version of this work appeared in [5]. The controller and the swarm model was based on our earlier work in [6, 4] (also see chapter 2) which introduced an aggregation and pattern generation algorithm for multi-agent systems. Aggregation strategies of MAS were introduced by many researchers; behavior based aggregation [72, 48], aggregation based on attraction/repulsion forces [39, 40]; and theoretical frameworks and applications of swarm aggregation were presented in [53, 66, 126]. Unlike aggregation, shape formation of multi-agent systems need more sensing capabilities and enhanced computational power in agents. Some authors introduced artiﬁcial potential functions [127, 41] while some used speciﬁc locations for agents to form the shape [70], which may not be suitable to be used in highly hostile environments such as battle ﬁelds. Autonomous formation control of land vehicles, space and air crafts are highly discussed in the recent past [128, 129, 130, 131, 132, 63, 133, 134, 135] introducing both centralized and decentralized controllers and presenting approaches to overcome common problems such as communication limitations, obstacle avoidance etc. The autonomous formation control of aircrafts, described in [136], presents a decentralized approach to control and reconﬁgure close-formations, utilizing the communication within the group. The authors make use of Dijkstra algorithm to select the optimal conﬁguration of the formation by addressing the communication links as in a shortest path problem. Also authors provide reconﬁguration schemes for formation in the case of loss of air craft(s) or failure of communication (either transmitter or receiver). In [85, 109, 137, 74] authors introduce contour based pattern generation methods using multiple robots (agents), where members of the swarm are guided to generate contour. Whereas in this paper the guided weapons are controlled by an algorithm that positions a multi-agent system into a shape deﬁned by a given contour while avoiding collisions. 4.2 Two-stage controller The controller introduced in this chapter is based on the controller introduced in the chapter 3. The special feature in this multi-agent pattern generation model is that it consists of a two stage control architecture which switches between stages, depending on the position of the swarm. Compared with the single stage controller used in the chapter 3, the two-stage controller eliminates the possibilities of any co-lateral damages in the weapon deployment system introduced in this chapter, ensuring that all the weapons lies inside the desired contour / area when they reach the ground. To achieve this, we deﬁne a minimum release height for weapon deployment which is based on the distance to the area, physical characteristics of the weapons (mass, speed etc.) and, the size and shape of the target area. The horizontal motion of the weapon system is governed by the artiﬁcial formation force based controller, while the vertical motion is modeled as free fall under the gravity. In this section, we ﬁrst introduce the basic controller for horizontal motion followed by the vertical motion model. For the analysis of the weapon system behavior the followings are assumed; • Weapons are of identical physical properties (such as mass, mobility etc,.). Chapter 4. Application Case Study: Swarming Guided Weapons 45 • Weapons are point masses i.e. without any physical dimensions. • Each weapon has instantaneous and error free localization capabilities. • The communication network of the weapon system can transmit the data (of any size) to all the weapons within the group instantaneously, i.e. without delay. • Weapons do not encounter any disturbances (such as air pockets, no-ﬂy zones) while in the ﬂight. • Weapons are released at the same height. • The drag constant and the reference area for the drag force remain constant throughout the ﬂight. • Density of the air remain constant during the time of ﬂight. Basically above assumptions were made in order to reduce the system complexity in the controller analysis phase and to highlight the basic aggregation and shape formation algorithm. But in later sections of the paper we relax these assumptions and introduce a weapon system model which can closely resemble a system consisting of real world gliding weapons. 4.2.1 Horizontal Motion Consider a weapon system consisting of N number of identical weapons operating in two dimensional Euclidean space. (Note that in deﬁning the horizontal motion controller we consider the weapon system as if they were moving on a 2D plane.) In this context we consider the problem of navigating and positioning the above weapon system into a shape bounded by a simple closed contour γ deﬁned in the complex plane, while spreading weapons inside the contour uniformly. The horizontal state of the weapon i is described by ⎡ ⎤ zi ⎢ ⎥ ⎥, (4.2.1) Xi = ⎢ ⎣ ⎦ z˙i where zi ∈ C, represents the position of the ith weapon in 2D complex plane. Let z be a point on γ, i.e. z ∈ γ. Before stating the weapon system model, we deﬁne α = 1 0 and β = 0 1 . Then T is determined by the the horizontal state of the whole weapon system, x = X1 X2 X3 ... XN continuous time dynamic model described by, x˙ = Ax + Bu, where and (4.2.2) , A = diag Aˆ N ×N 1 ˆ B = diag B m N ×N ⎡ Aˆ = ⎣ ⎤ 0 1 0 0 ⎡ ˆ=⎣ ⎦, B (4.2.3) (4.2.4) ⎤ 0 ⎦. (4.2.5) 1 In (4.2.4), m is to our assumptions, notice that each weapon’s position the mass of a weapon. According information ( αX1 αX2 . . αXN ) is available to the communication network. In other words, each weapon know the location matrix without a delay. 46 Chapter 4. Application Case Study: Swarming Guided Weapons 3000 Ui,1 rc Y−Coordinate [m] 2800 Yes C c := if |zi-zc|>rc for any i No 2600 2400 2200 2000 z c 1800 1600 1400 1200 1000 Ui,2 0 500 1000 1500 2000 X−Coordinate [m] (a) Two tier architecture of the controller (b) Circle inside the shape Figure 4.1: Components of the two stage architecture The control input u in (4.2.2) consists of, T u= where (4.2.6) u1 u2 u3 ... uN ⎧ ⎨ U i,1 ; remains operative while |zi − zc | > rc for any i ui = ⎩ Ui,2 ; active after the ﬁrst stage elapsed (4.2.7) The artiﬁcial formation force based controller operates in two stages; the ﬁrst stage starts as soon as the weapon system is deployed (initialized) and it continues until all the members are converged into a circle of radius rc . rc is the radius of the largest circle which can be enclosed inside the desired contour, having the center of the circle on the center of mass of the contour. The second stage starts once the condition for the ﬁrst stage are no longer satisﬁed and it lasts until the weapon system reaches the surface. Remark 4.2.1. Once the second stage of the control algorithm is initialized it does not switch back to the ﬁrst stage. Before introducing the controllers and the artiﬁcial forces, we deﬁne the followings; N zcm = (zi ) i=1 N z dz zc = γ dz , l(γ) = l(γ) (4.2.8) γ where zcm , zc and l(γ) represents the center of mass of the weapon system, the center of mass of the contour and the length of the contour respectively. The ﬁrst stage controller is as follows; Ui,1 = Fi,A1 + Fi,M − Fi,F , (4.2.9) and the second stage controller is in the following form; Ui,2 = Fi,A2 + Fi,R2 + Fi,M − Fi,F . (4.2.10) The artiﬁcial attraction force components of the controller stages, (Fi,A1 and Fi,A2 ) are deﬁned as, (4.2.11) Fi,A1 := kA1 (z − αXi ) dz , γ and Fi,A2 := kA2 (1 − n(γ, αXi )) γ (z − αXi ) dz . (4.2.12) Chapter 4. Application Case Study: Swarming Guided Weapons 47 Fi,R2 is the artiﬁcial repulsion force on the ith weapon from the shape, and is in the following form, Fi,R2 := kR2 n(γ, αXi ) γ (αXi − z) dz . αXi − z3 (4.2.13) n(γ, zi ) in the above (4.2.12) and (4.2.13) represents the Cauchy Winding Number of γ about zi ∈ C, having the following from, 1 dz n(γ, zi ) = 2πi γ z − zi Remark 4.2.2. Clearly n(γ, αXi ) = 1 when weapon i is inside γ 0 when weapon i is outside γ ensures that the term Fi,A2 in (4.2.10) vanishes only if the weapon is inside the contour and the term Fi,R2 vanishes only if the weapon is outside the contour. Fi,M in (4.2.9) and (4.2.10) refers to the resultant artiﬁcial repulsion force acting on the ith weapon from the remaining weapons of the system (inter weapon collision avoidance force), i.e: ⎡ Fi,M := kM ⎣ N j=1j=i ⎤ (αXi − αXj ) ⎦ , αXi − αXj 3 (4.2.14) Fi,F in (4.2.9) and (4.2.10) is given by, Fi,F = kF βXi , (4.2.15) which acts as a damping force. The constants kA1 , kA2 , kR , kM , kF ∈ R+ are the weighing parameters of the respective artiﬁcial forces. Bounds for kA1 , kM and kF with respect to stability and cohesiveness of the weapon system are obtained in the analysis presented section in 4.3.1. For notational simplicity, we use Fi,A1 , Fi,A2 , Fi,R2 , Fi,F and Fi,M terms instead of the functionals Fi,A1 (xi , γ), Fi,A2 (xi , γ), Fi,R2 (xi , γ), Fi,F (xi ) and Fi,M (xi ) respectively. 4.2.2 Vertical Motion In the vertical motion model we consider free fall motion, i.e. the weapon motion is governed only by the gravitational acceleration and the resisting drag force on the weapon. Remark 4.2.3. Drag force (Fd ) on an object moving in a ﬂuid is given by, 1 Fd = ρAr Cd V 2 2 (4.2.16) where Ar -Reference area for the drag force, Cd -Drag constant, ρ-Density of the ﬂuid and Vo is the speed of the object. Using that, we derive the motion dynamics of a weapon in the vertical direction as, dVt ρAr Cd 2 + V = g, dt 2m t where Vt is the vertical velocity of the weapon and g is the gravitational acceleration. (4.2.17) 48 4.2.3 Chapter 4. Application Case Study: Swarming Guided Weapons Discussion The two stage controller introduced in this paper is rather diﬀerent to the initial version of the swarming guided weapons [138], in terms of the behavior. In deploying weapons, such multistage architecture becomes useful, since positioning all the weapons inside the contour has a signiﬁcant advantage in minimizing collateral damages. In the ﬁrst stage, the Fi,A1 artiﬁcial attraction force navigates the whole weapon system toward the shape and assemble inside a given circle around zc . Among the artiﬁcial formation forces in the stage two, Fi,R2 spreads the weapons inside the shape, while Fi,A2 attracts any weapon that moves out of the contour boundary. In both controllers Fi,M is repulsing the weapons from each other which prevents collisions between the weapons. Fi,F is the artiﬁcial friction force exerted on each weapon, forcing the weapon to a complete stop when the artiﬁcial formation forces are balanced. This is to ensure that the weapons reach a desirable equilibrium state in the horizontal motion. 4.3 Analysis of Release Height and Weapon Behavior The theoretical analysis of the weapon system’s behavior is presented; behavior under the horizontal controller is investigated followed by the vertical motion analysis. Since the controller consists of a two stage architecture, we investigate the properties of each stage separately. For the ﬁrst stage controller, we derive the conditions for stability and cohesiveness with an expression for the time of convergence. Then the equilibrium positions under the second stage controller is investigated. Finally with the vertical motion analysis we present an important result on the release height of the weapon system, which ensures every weapon lies inside the desired target contour at the time of impact. 4.3.1 Cohesive Stage From the two stages of the controller, the ﬁrst stage is called as the “Cohesive Stage”, in other words the weapons are attracted into the shape thus the system is in converging state. With the analysis on the cohesive stage we describe the motion of the complete weapon system and introduce the conditions for stable convergence and the cohesiveness. Then the analysis is extended to determine the time required for the weapon system to converge into a circle deﬁned at the centroid of the contour. Motion of the Complete Weapon System Firstly, we examine the behavior of the complete weapon system where it is considered as one complete object in which the motion is governed by the resultant artiﬁcial force (R), R = RA1 − RF + RM . (4.3.1) With this, the equation of motion of the weapon system can be described by, m ε¨ + kF ε˙ + kA1 l(γ) ε = 0, (4.3.2) where ε = (zcm − zc ), with ε˙ = z˙cm , ε¨ = z¨cm . Remark 4.3.1. Notice that in (4.3.1); RM , which represents the resultant collision avoidance term is zero as, N N (αXi − αXj ) = 0. RM = αXi − αXj 3 i=1 j=1j=i RA1 , the resultant artiﬁcial attraction force from the contour, is expressed as, RA1 = kA1 N i=1 γ (z − αXi ) dz , Chapter 4. Application Case Study: Swarming Guided Weapons 49 and using deﬁnitions for zc , zcm and l(γ), the above can be stated as: RA1 = l(γ)N kA1 (zc − zcm ) . RF , represents the resultant artiﬁcial damping (friction) force, and is in the form of, RF = N kF (z˙cm ) . Therefore, the net resultant force on the complete weapon system (this force is applied on the center of mass of the system) is, R = N l(γ)kA1 (zc − zcm ) − N kF (z˙cm ) , and hence the motion dynamics of the weapon system can be described by (4.3.2). With the above motion dynamics of the weapon system, we obtain our ﬁrst result; the center of mass of the weapons (zcm ) moves toward the shape. A formal expression of above statement together with the proof is given by the following Proposition. Proposition 4.3.1. Consider the weapon system model described by (4.3.2), the motion of the center of mass of the weapons (zcm ) is in the direction of decreasing ε (i.e. toward the center of mass of the contour (zc )). 1 1 Proof. If we select a Lyaponov function candidate as Vcm = mε˙ε˙∗ + kA1 l(γ)εε∗ , then the derivative 2 2 V˙ cm is bounded by, ˙ 2. V˙ cm ≤ −kF ε ˙ = 0, the only invariant point is the origin (i.e. ε = ε˙ = 0), using extended version ˙ 2 > 0, ∀ε Since kF ε of Lyapunov’s method proposed by LaSalle and Lefschetz (Theorems VI and VII in [106]) we can state that the system is asymptotically stable at the origin, which proves our assertion. Basically, this Proposition says that the motion of the center of mass of the weapons is toward the center of mass of the contour and this holds, regardless of the motions of individual weapons with respect to zcm . Remark 4.3.2. Using the properties of second order ODEs one can state that; smooth motion of the weapon system (i.e. damped motion dynamics) toward the target contour (zc ) can be obtained if the conditions m, kA1 , kF > 0 and kF ≥ 2 m kA1 l(γ) are satisﬁed. Motion of a Single Weapon Proposition 4.3.1 shows only the behavior of the complete weapon system, but it does not say anything about the behavior of individual weapons in the cohesive stage. Next we investigate the behavior of an individual weapon of a speciﬁc weapon system, where the weapons are spaced than a selected value, called as “X Weapon System”. Further, we introduce a condition for a “X Weapon System” to be cohesive under Fi,A1 force in the Proposition to follow. Deﬁnition 4.3.1. A weapon system S is deﬁned as “X Weapon System”, if there exists positive constants Δ, δ that satisfy the following conditions simultaneously for all i, j ∈ S and i = j. 1. dij ≥ δ + Δ, i zi − zcm Δ 3 , < 1+ 2. zi − zcm δ 50 Chapter 4. Application Case Study: Swarming Guided Weapons where N i = dij = zi − zj and zcm zj j=1;j=i N −1 . i is the center of mass of the weapon system without the ith weapon. In the above deﬁnition, zcm In the ﬁrst condition of the “X Weapon System” deﬁnition, we impose a constraint on the distance between weapons in the system. That is the distance di,j is larger than a selected value (δ+Δ). From the second condition we set the ratio between δ and Δ, in which the ratio moves toward zero with increasing number of weapons in the system (see Remark 4.3.3). Remark 4.3.3 (Proof for “X Weapon System” δ and Δ ratio). From the deﬁnition 1, the ratio between δ and Δ can be written as follows, N zj 3 j=1;j=i zi − N −1 Δ > 1+ N δ zj zi − j=1 N ⎛ ⎞ N ⎠ zi (N − 1) − ⎝ z + z + z j i i 3 j=1;j=i N N Δ > 1+ = N −1 N δ N −1 zi N − zj j=1 Δ > δ 3 N N −1 −1 ⇒ Δ → 0, when N → ∞ δ Using the deﬁnition of “X Weapon System” we derive that the artiﬁcial collision avoidance force (Fi,M ) on any weapon in the system is bounded, as presented in the following lemma. Lemma 4.3.2. For a weapon of a “X Weapon System”, the magnitude of the artiﬁcial collision avoidance kM (N − 1) zi − zcm , force is less than δ3 Proof. Fi,M = kM N (zi − zj ) . 3 d ij j=1,j=i (4.3.3) Using the condition 1 of the “X Weapon System”, we have Fi,M < kM (N − 1) i zi − zcm . 3 (δ + Δ) (4.3.4) Then using the condition 2, the following can be derived; Fi,M < kM (N − 1) zi − zcm . δ3 (4.3.5) Chapter 4. Application Case Study: Swarming Guided Weapons 51 The above result is an upper bound for the magnitude of the inter weapon repulsion force Fi,M in a “X Weapon System”, which we use in the proceeding sections. Before investigating more into the behavior of a single weapon, we deﬁne the error between zi and zcm as υi = (zi − zcm ); resulting υ˙ i = (z˙i − z˙cm ) zi − z¨cm ). From the weapon system model introduced in (3.1.2), the motion of the ith weapon and υ¨i = (¨ in the cohesive stage can be described by, N 1 (zi − zj ) z¨i = kA1 × l(γ)(zc − zi ) + kM − kF z˙i (4.3.6) m zi − zj 3 j=1,j=i in which we used, Fi,A1 = kA1 γ (z − αXi ) dz = kA1 × l(γ) (zc − zi ) . (4.3.7) From (4.3.2) and (4.3.6), m υ¨i + kF υ˙ i + kA1 l(γ) υi − kM N (zi − zj ) 3 = 0, z − z i j j=1,j=i (4.3.8) which describes the motion of a single weapon with respect to the center of mass of the weapon system. In the following Proposition we introduce a condition for a “X Weapon System” to be cohesive under Fi,A1 . Proposition 4.3.3. Consider a weapon i of a “X Weapon System” operating in the ﬁrst stage of the (N − 1) kA1 , then the motion of that weapon is in the direction of > 3 controller, at any given time; if kM δ × l(γ) decreasing υi (i.e. toward the center of mass of the weapons (zcm )). Proof. Choosing a Lyapunov function candidate for the weapon i as 1 1 kM (N − 1) ∗ ∗ Vi = mυ˙ i υ˙ i + υi υi kA1 l(γ) − 2 2 δ3 and taking derivatives, we can show that V˙ i is bounded by, ⎛ ⎞ N (zi − zj ) kM (N − 1) υi ⎠ υ˙ i . V˙ i ≤ −kF υ˙ i 2 + ⎝ kM 3 − δ3 z − z i j j=1,j=i Since we consider a weapon of a “X Weapon System”, we have (from Lemma 4.3.2), N (zi − zj ) (N − 1) zi − zcm 3 < δ3 j=1,j=i zi − zj and hence we have, V˙i < −kF υ˙i 2 (4.3.9) (4.3.10) (4.3.11) (4.3.12) which proves the assertion. The above Proposition is valid only for the cohesive stage of the controller, and does not hold once the system switches to the second stage. Remark 4.3.4. If the δ and Δ values were selected to satisfy “X Weapon System” conditions even when all the weapons are inside the desired radius (rc ), then using the above Proposition we can easily select kA2 for the second stage controller which guarantee the convergence of any weapon staying outside the contour. 52 Chapter 4. Application Case Study: Swarming Guided Weapons Remark 4.3.5. The following procedure can be employed to select the parameters which ensure that the weapon system satisﬁes the “X Weapon System” conditions when achieving the cohesive behavior throughout the ﬁrst stage of the controller; 1. Determine the number of weapons assigned to the target area. 2. Deﬁne the radius of the circle (rc ) around zc . 3. Determine the minimum distance between weapons (dm ) when all of them are populated inside that circle (see [139, 140]). Then select the values for δ and Δ which “X Weapon System” satisfy N 3 conditions for the above minimum space, i.e. dm ≤ δ + Δ and Δ δ > N −1 − 1 (see Remark 4.3.3). 4. Use Proposition 4.3.3 and δ to determine the ratio between kA1 and kM . Remark 4.3.6. Consider a weapon system released far away from the desired target area, having an artiﬁcial force based controller described in (4.2.9) and satisfying “X Weapon System” hypothesis. Then Propositions 4.3.1 and 4.3.3 infer that the overall motion of a weapon (in the cohesive stage of the controller) is toward the center of mass of the contour. Time of Convergence In this section we derive an expression for the upper bound of the time required for the weapon system to converge into a circle with radius rc around the centroid of the contour (zc ). The result we obtained for the time of convergence is used to determine the release height of the weapon system as explained in proceeding sections. Here also we assume the weapons system behaves as a “X Weapon System” and satisfy the conditions for stable convergence with over damped dynamics (i.e. kF > 0 and kF > 2 m kA1 l(γ)). √ √ With the above assumptions we can state the following, a2 > 2 a1 a3 and a2 > 2 a1 a4 , where a1 , kM (N − 1) respectively. a2 , a3 & a4 refers to m, kF , [kA1 l(γ)] & kA1 l(γ) − δ3 First we obtain a result on the time of convergence for a general second order diﬀerential equation as described in the following lemma. Lemma 4.3.4. Consider a second order ordinary diﬀerential equation in the form of, φ¨ + b1 φ˙ + b2 φ = 0 having a general solution in the form of φ(t) = c1 eλφ,1 t + c2 eλφ,2 t , with the following properties; (i) λφ,1 , λφ,2 < 0, (ii) λφ,1 < λφ,2 Let φ(td ) = φd and φ(0) = φ0 . For such a system, the following statement holds; φd ln c1 , (4.3.13) td < λφ,1 b21 − 4b2 , where, λφ,1 = 2 ! ! " " b1 b1 −b1 + b1 2 − 4b2 φ0 φ0 , c1 = 1+ 2 1− 2 and c2 = . λφ,2 = 2 2 2 b1 − 4b2 b1 − 4b2 −b1 − Proof. For a second order system with the solution φ(t) = c1 eλφ,1 t + c2 eλφ,2 t , it is always possible to ﬁnd ´ with the solution, ϕ = c1 eλφ,1 t such that, a ﬁrst order system ϕ˙ = Aϕ ∀t, φ(t) < ϕ(t). (4.3.14) Chapter 4. Application Case Study: Swarming Guided Weapons 53 2000 |υ (t)| i |ε(t)| ψ(t) ψ(t), |ε(t)|, |υi(t)| 1500 1000 500 0 t(υd) t(ε ) d t(ψ ) d −500 0 0.5 1 1.5 2 2.5 3 3.5 4 Time [s] Figure 4.2: Behavior of φ(t), υi (t) and ε(t) Thus, the time of convergence of both systems to a common output (d) relates as below. ∀d, tφ,d < tϕ,d . With that we get, ln td = tφ,d < φd c1 (4.3.15) λφ,1 (4.3.16) Since all the components in (4.3.2) are along the same vector, the motion dynamic system for the weapon system described in (4.3.2) can be written (as a scaler system along ε) as, ε + a2 ε ˙ + a3 ε = 0. a1 ¨ (4.3.17) The solution for (4.3.17); ε(t) = c1 eλ1 t + c2 eλ2 t have the following properties (refer Remark 4.3.7), (4.3.18) λ2 , λ1 < 0 and λ1 < λ2 √ (As a2 > 2 a1 a3 ) Also the motion of a single weapon in (4.3.8) can be described by the following second order system (as a scalar system along υi ); (4.3.19) a1 υ¨i + a2 υ˙i + a4 υi < 0. And the solution for the above system, υi (t) < c3 eλ3 t + c4 eλ4 t have the following properties (refer Remark 4.3.7), (4.3.20) λ4 , λ3 < 0 and λ3 < λ4 √ (As a2 > 2 a1 a4 ) Since systems (4.3.17) and (4.3.19) satisfy the properties of the Second order ODE described in Lemma 4.3.4, we have the followings; (Refer ﬁgure 4.2 for behavior of ε(t),υ(t) and corresponding ψ(t)) 1. Time for the center of mass of the complete weapon system (zcm ) to move into a circle around zc having radius d (using properties of the equation (4.3.17)), d ln c1 . (4.3.21) t(d ) < λ1 (We deﬁne d as the radius of a circle centered at zc , which is inﬁnitesimally small such that a point inside the circle can be approximated to be on zc ) 54 Chapter 4. Application Case Study: Swarming Guided Weapons 2. Time for the weapon at the most distant location from the center of mass of the weapons (zcm ) to move into a circle around zcm , with radius rc (using properties of the equation (4.3.19)), rc ln c3 t(rc ) < . (4.3.22) λ3 Thus we can state the following condition about the time of convergence (tc ); tc < t(d ) + t(rc ) (4.3.23) Note that the weapon system will switch to the second stage of the controller at the moment all the weapons are converged in to the radius rc around zc . Thus the time of convergence will be the same as the time when the system switches to the second stage of the control architecture. Remark 4.3.7 (Coeﬃcients of the Solution). a22 − 4a1 a3 λ1 = 2a1 −a2 + a22 − 4a1 a3 λ2 = 2a1 −a2 − a22 − 4a1 a4 λ3 = 2a1 −a2 − a22 − 4a1 a4 λ4 = 2a1 ! " a2 υi (0) 1+ 2 c3 = 2 a2 − 4 a1 a4 ! " a2 υi (0) 1− 2 c4 = 2 a2 − 4 a1 a4 ! " a2 ε(0) 1+ 2 c1 = 2 a2 − 4 a1 a3 ! " a2 ε(0) 1− 2 c2 = 2 a2 − 4 a1 a3 −a2 − 4.3.2 (4.3.24) (4.3.25) (4.3.26) (4.3.27) (4.3.28) (4.3.29) (4.3.30) (4.3.31) Release Height In deploying an airborne weapon system, the release height of the weapons becomes an important aspect in avoiding collateral damages. In this section we introduce a lower bound for the release height, which ensure that all the weapons are converged into the desired contour at the time of impact. We use the expression derived for the time of convergence in section 4.3.1 to determine the lower bound, as stated in the following Proposition. Proposition 4.3.5. Consider a guided weapon system, where the motion of the complete system is described by (4.3.2) and the motion of a weapon is described by (4.3.8). All the weapons will converge into the given geographical boundary (γ), if the release height of the weapons (hrel ) satisfy the following condition, 2m gρAr Cd tm log cosh hrel > ρAr Cd 2m Chapter 4. Application Case Study: Swarming Guided Weapons where, ln tm = rc c3 λ3 ln + d c1 55 λ1 Proof. Since the vertical motion of a weapon system is governed by (4.2.17), the vertical velocity of a weapon after time t is given by, 2mg gρAr Cd t . (4.3.32) tanh Vt (t) = ρAr Cd 2m Therefore the vertical distance traveled after t time can be derived as, 2m gρAr Cd d(t) = t . log cosh ρAr Cd 2m (4.3.33) Form time of convergence, we have ln tc < rc c3 λ3 ln + d c1 λ1 = tm . (4.3.34) Thus t = tm in (4.3.33) will ensure that the weapon system will converge into a circle of radius rc around zc within the vertical distance d(tm ) which proves our assertion. The above Proposition uses the time for the weapons system to converge into the given geographical shape in order to express the vertical distance traveled within that time as a lower bound for the release height. Note that, it does not say anything about the time taken for uniform distribution of weapons inside the shape or the corresponding release height. 4.3.3 Summery of the analysis From the preceding analysis, the behavior of the weapon system can be summarized as follows, • In the ﬁrst stage of the controller, the weapon system (center of mass of the weapons) moves toward the center of mass of the contour (zc ) regardless of the motion of individual weapons. This motion will continue until all the weapons are converged into the pre-deﬁned circle around zc . • In the ﬁrst stage of the controller, the individual weapons will move toward zcm while the conditions for “cohesive behavior” are satisﬁed (see Proposition 4.3.3). That is when the weapons are suﬃciently spaced from each other, the collision avoidance force is negligible in comparison to the attraction force. Also, from the analysis for the cohesive stage, we can conclude that the motion of each weapon is toward zc while the “X Weapon System” conditions are satisﬁed. • First order approximations of the weapon system dynamics are used to determine the time of convergence. This provides an upper bound for the time required for the weapon system to converge into the pre-determined circle around zcm (radius rc ). Using the time of convergence result, a release height of the weapon system was introduced which guarantees that all the weapons lie within the targeted geographical area at the time of impact. • During the second stage of the controller, the weapon system reaches a stable equilibrium state with the center of mass of the weapon system (zcm ) moved to zc . The theoretical analysis provided is only for shape contours with more than one intersecting symmetrical axes. Since the behavior of the second stage controller is exactly same as the controller introduced in the chapter 3, the analysis of this part is not performed in this chapter (see chapter 3 for more details). 56 4.4 Chapter 4. Application Case Study: Swarming Guided Weapons Discussion on Implementation Issues In this section we discuss the issues to be considered when implementing the proposed architecture in a real world scenario. The proposed algorithm can eﬀectively be used in the navigation of airborne guided weapons launched by either ground deployment system (e.g. MLRS) or air deployment system. The only requirement for the algorithm is that, at the initialization of the controller, all the weapons are in suﬃcient height above the target, as speciﬁed in the previous section. First we discuss the modiﬁcations for the controller in order to compensate for the implication in the practical implementation of (4.2.7). Further, the implications of the assumptions (in (4.2.7)) are discussed together with possible remedial approaches using realistic error models implemented in simulation case studies. Also the possible third stage of the controller to overcome diﬃculties in “deploying the weapons at the same height” is also proposed. 4.4.1 Controller Modiﬁcation for Practical Implementation Upon the introduction of the controller and in the behavioral analysis of the weapon system, we considered the weapons were point masses (i.e. without any physical dimensions) and assumed that they can exert virtually any artiﬁcial force (i.e. unbound forces). Those assumptions alone degrades the applicability of the algorithm in real world weapons. In the following text we introduce the modiﬁcations to account for above deﬁciencies in the control algorithm. Please note that the issues discussed in this section can be applied to any robotic system which uses the controller introduced in the chapter 2. Physical Size of Weapons For this case we consider weapons with physical dimensions, length (lm ) and width (wm ). Let lm > wm , then we deﬁne the operational diameter of a weapon (d0 ) as d0 = k0 × lm ; where k0 > 1 is considered as the safety factor for collision avoidance (similar to safety factor in mechanical/structural designs; ko can be chosen to suite the maximum speed of motion, importance in collision avoidance etc). Then the modiﬁed artiﬁcial force for collision avoidance is as follows: ⎡ ⎤ N 1 d ij ⎦, (4.4.1) F#i,M := kM ⎣ dij (dij − do )2 j=1j=i where dij = (αXi − αXj ). Comparison of F#i,M and Fi,M is illustrated in Fig. 4.3. Actuator Limitations Next, we modify the force function to eliminate the problem of unrealistic accelerations, by introducing maximum force parameters into the resultant force function. The controller (ui ) with modiﬁed force function is as follows, (4.4.2) ui = F#iR where, F#iR = ⎧ ⎨ FiR ⎩ Fi,max if FiR < Fi,max if FiR ≥ Fi,max , (4.4.3) in which FiR is the desired resultant artiﬁcial force on ith weapon of the system and Fi,max refers to the maximum possible force that can be exerted by the actuators. Other than the actuator limitations which limits acceleration of the weapon, the resisting drag force limits the velocity of a weapon to the terminal velocity. Then the horizontal velocity of the weapon is Chapter 4. Application Case Study: Swarming Guided Weapons 57 5 Fi,M Modified F Force Magnitude 4 i,M 3 2 1 dij 0 −1 Physical size of a weapon −2 −3 wm Operational diameter (d ) −4 lm 0 d0 −5 0 2 4 6 8 10 Distance from weapon [m] (a) (b) Figure 4.3: Eﬀect of physical size of weapons on the collision avoidance force. Here the operational diameter (d0 ) is selected as 2m. Note that the modiﬁed function increases the repulsion force from the neighboring weapon, when the center of the weapon comes closer to the 2m limit. The sub ﬁgure (b) represents a real world example describing the scenario, where the robots / agents are represented by car type vehicles determined by, m z˙i d2 (zi ) ρAr,h Cd,h z˙i 2 = F#iR + 2 dt 2 z˙i (4.4.4) where Ar,h and Cd,h represents reference area and drag coeﬃcient for horizontal motion respectively. Chattering Eﬀect The nature of artiﬁcial forces in stage two of the controller (which is similar to the controller in [138]) may cause potential chattering problem. (see Figure 4.4 for behavior of the forces). That is, when the controller is in the second stage, if a weapon moves out of the contour, the magnitude of the attraction force may not be suﬃcient to attract that weapon into the shape when large number of weapons are already staying inside the contour. This problem can successfully be eliminated by modifying the Fi,A2 force as expressed in (4.4.5). In the modiﬁed function, an additional term is included which increases the attraction force when the weapon is staying closer to the contour. Also this addition improves the uniformity of the “Artiﬁcial Formation Forces” in either side of the contour. ˜ Fi,A2 := (1 − n(γ, αXi )) kA2 (z − αXi ) dz + γ (z − αXi ) (4.4.5) kAC 3 dz γ z − αXi In the above expression kAC is the weighing parameter of the force component which dominates when the weapon is closer to the contour. Alternatively, the condition provided in Proposition 4.3.3 can be used to deﬁne “X Weapon System” parameters and to select a kA2 parameter which ensure cohesiveness of the weapons under Fi,A2 force. 58 Chapter 4. Application Case Study: Swarming Guided Weapons 5000 Fi,R2 F i,A2 Modified F 4500 i,A2 Force [N] 4000 3500 3000 2500 2000 1500 1000 500 0 0 200 400 600 800 1000 Distance From Center [m] Figure 4.4: Behavior of stage two “Artiﬁcial Formation Forces” at the contour boundary. For better visualization of the changes in forces, the Fi,R2 & Fi,A2 (modiﬁed) forces are limited up to 5000N . 4.4.2 Implementation, Technologies and Error Models The proposed algorithm for controlling a weapon system has two basic implementation steps; initial parameter selection (design) and deployment. Prior to the deployment, the target contours are to be clearly deﬁned and the corresponding contour functions relative to the weapon coordinate system (e.g. GPS) are to be generated. Considering the weighing parameters of the artiﬁcial force functions (i.e. kM , kF , kA1 .. etc.), the proper parameters have to be selected depending on the application and the constrains provided in the analysis sections. The next step is to deploy the weapons programmed with designed contours and group parameters. Also the algorithm provide provisions to change the contour functions and parameters to add/remove weapons in an already deployed system. But this needs eﬀective communication between control center (base station) and the group. The behavior of the weapons in such situations are presented in the simulation section. Remark 4.4.1. In the pre-deployment stage, the targets can eﬀectively be identiﬁed using satellite maps. Also real-time satellite coverage and aerial video updates from UAV’s can be used to determine the shape/location changes in the target contour (specially when the target is moving), for dynamic parameter modiﬁcations of the weapon system. 4.4.3 Obstacle Avoidance This is one of the most important aspects in real world implementation of the algorithm (see [141, 142, 143, 144]). Here we assume that the obstacle is previously identiﬁed and can be deﬁned by a simple closed contour in the 2D plane. Then the artiﬁcial force acting on ith member from the obstacle O is as follows; Fi,O := kO γO (αXi − zO ) dzo , αXi − zO 4 (4.4.6) where kO is a weighing parameter determining the magnitude of the force. Terms γO ∈ C and zO ∈ C are the contour (simple closed) deﬁning the shape of the obstacle and a point on that contour respectively. 1 as the zi − zo 3 magnitude of the force from each point, which enables the swarm to navigate closer to the obstacle boundary when deviating from the path. This form of a force function is specially useful for obstacles located closer to the target contours, such that the repulsion force from the obstacle do not prevent agents from converging into the shape. Also this deﬁnition allows us to include obstacles inside the target contour enabling the agents to acquire complex shapes. Remark 4.4.2. In deﬁning the above artiﬁcial force for obstacle avoidance, we used Chapter 4. Application Case Study: Swarming Guided Weapons 59 Initial positions @t=0 Y−Coordinate [m] 500 0 −500 Final positions @t=1000 −1000 −1500 −1000 −500 0 500 1000 1500 X−Coordinate [m] (a) Y−Coordinate [m] −600 −800 −1000 −1200 −1400 −1600 −1800 0 200 400 600 800 1000 1200 1400 1600 X−Coordinate [m] (b) Figure 4.5: Motion of the swarm in presence obstacles Contour Figure(a)-Target Figure(a)-Obstacle1 Figure(a)-Obstacle2 Figure(a)-Target Figure(a)-Obstacle1 Figure(a)-Obstacle2 Figure(a)-Obstacle3 a 5 3 4 5 3 4 4 b 1 1 1 1 1 1 1 c 0.5 0.0 0.0 0.5 0.0 0.5 0.2 d 80 30 70 50 30 20 20 Table 4.1: Parameters used in shape generation We present two simulation case studies to demonstrate the behavior of the swarm in the presence of obstacles. In the ﬁrst case (Figure 4.5.(a)) the vehicles (mobile robots) are in a line formation (for example along a road or in a convoy) and the target contour is located beyond two obstacle contours. As illustrated in the ﬁgure, the mobile robots successfully avoid both obstacles and form the desired shape by t = 1000s. In the second case, we consider a situation where mobile robots are randomly distributed around the target contour. Here we used two obstacles outside the target contour and one obstacle inside the target. Here also the mobile robots successfully maneuvered around the obstacles and moved into the desired shape. (The parameters listed in table 4.1 are used for this simulation case.) 60 Chapter 4. Application Case Study: Swarming Guided Weapons Case case (a) case (b) ka 5 × 10−3 5 × 10−3 kr 5 × 103 5 × 103 km 7 × 105 5 × 105 Table 4.2: Weighing parameters for artiﬁcial forces Figure 4.6: Robots navigate using restricted inter-member force due to limited communication range. Localization and communication issues For successful implementation of the algorithm, the ideal weapons need the following capabilities; (i). Instantaneous and error free self localization. (ii). Knowledge of location of all other members of the group without delay (using communication network) Here we discuss the practical implementation issues and some technologies which provide near ideal capabilities to the weapons. Since our weapons system is supposed to have GPS/INS navigation system which eliminate short range inaccuracies of GPS other than the random error of localization, the localization error can be modeled as follows; (4.4.7) zi = zˆi + ηi where zˆi is the actual position and ηi refers to the random noise (σηi = GPS error and μηi = 0). In the shape formation algorithm, knowledge of position of all the weapons is important in determining the collision avoidance force (Fi,M ). This location information is sent through a wireless RF links (or communication network). However, the ability to communicate with each other at the same time can be restrictive in real world applications. Even if CDMA2 technology [145] was used to communicate with many devices at once, due to high degree of interferences, the eﬀectiveness of the communication will degrade with increasing number of weapons in the group. The interferences can be minimized using transmission power control, although it reduces the range of transmission. Wireless mesh networking technology ([146, 147]) can be a better solution since it enables handling large data ﬂows within large number of nodes [148]. Delays in data transmission (via routing) and range limitations [149] are some drawbacks in the wireless mesh networking. However the eﬀect of range limitations will not appear in communication within the weapon system. This is due to the obstacle free environment in upper atmosphere where the weapons operate. Although near ideal wireless communications within the group can be achieved, the problem of electronic and radio jammers in military operations will degrade the communication capabilities signiﬁcantly. This arise the need of secondary (backup) method of collision avoidance (such as sonar/laser range and bearing estimation) which can locate at least the neighboring weapons. Thus the collision avoidance force 2 CDMA (Code Division Multiple Access) technology enables simultaneous access of the whole frequency spectrum without time divisions, increasing the number of wireless nodes connected to a single station in an instance. Chapter 4. Application Case Study: Swarming Guided Weapons 61 Altitude bracket of weapon release Travel height in the "cohesive" stage Stage Switching altitude Altitude for "Freezing" the relative motion Target area Range of the jammer Earth Surface Figure 4.7: Communication jammer range and altitudes of operation function model for a weapon system with communication failures (limitations) can be given as follows; ⎡ ⎤ N d 1 ij ⎦ , ∀j (4.4.8) F#i,m := km ⎣ dij (dij − do )2 j=1j=i where dij < dc . Here dc refers to the radius around a weapon in which the neighboring weapons can be successfully located. For successful operation of the weapon collision avoidance force, a rough relative location estimate is suﬃcient. However the stage switching requires the position information of all the weapons in the system, thus communication jammers can eﬀectively degrade the performance of stage switching. Generally the eﬀective range of communication jammers are limited to a certain radius from the physical location of the jammer. Thus the above problem can be eliminated by selecting a release height for weapons which ensure that the weapons are switched to the second stage (see section 4.3.2 for vertical distance traveled in the cohesive stage) when reaching the eﬀective radius of the jammer (see ﬁgure 4.7). Upon the introduction of the controller we have made a restrictive assumption such that all the weapons are at the same height at the initialization of the algorithm. This means that the weapons in the system do not have relative altitude diﬀerences. However in a real-world battle ﬁeld environment specially for weapon deployments performed by diﬀerent air crafts, it may not be always possible to satisfy the above altitude criteria. This results in weapons operating in diﬀerent altitudes. In such instances, the weapons released at lower heights will reach the target ﬁrst (since we do not control the vertical motion of the weapons), triggering a loss of weapons event (see simulation for a demonstration of loss of weapons event). This causes redistribution of remaining weapons which is not intended. Above problem can be easily eliminated by introducing another stage to the controller, which “freezes” the positions of the weapons (relative to each other) once the ﬁrst weapon reaches a certain altitude bracket. Moreover, deﬁning the “freezing” altitude higher than the range of the jammers (see ﬁgure 4.7) will enable stable weapon control in the presence of radio/electronic jammers. Computational Issues The path generation in the proposed weapon system is a real-time and a decentralized process. That is each weapon calculates its own path (next position) based on the desired contour information, self location (state) information and the position information of other weapons in the system. This is a continuous process and the frequency of the path calculation (sampling rate) determine the navigational accuracy of the weapon system. Since the path planning needs computation of artiﬁcial forces consisting of line integrals, a signiﬁcant computational burden is imposed on the weapon control electronics. In the numerical evaluation of line integrals, the resolution of the contour deﬁne the accuracy as well as the time required for the calculation. There is a trade-oﬀ between accuracy and speed of the line integral calculation and hence the user must carefully select the resolution of the contour which best suits a particular application. 62 Chapter 4. Application Case Study: Swarming Guided Weapons E B D A C Target Area Figure 4.8: Deﬁning multiple weapon densities in a single target area. Green circles represent the circles with radius rc which are used for stage switching at corresponding target area Shape Generation and Uneven Weapon Distribution Populating the weapons into a pre-deﬁned ground target needs careful selection of the target contour which satisfy the “simple/closed” criteria as well as enclosing the complete target. Note that at the introduction of the controller, the target contour was deﬁned as a mathematical function in the complex domain. In reality, due to the complex geometries of the target area, deﬁning the target shapes as a mathematical function is not always possible. Moreover, the numerical computation of path planning requires the target contour as a set of coordinates. Such point based contour generation enables the user to deﬁne any odd shaped contour which covers the target area (see the simulation results in ﬁgure 4.13 for a weapon system assigned to a target generated as a series of points). Another major concern in military operations is the density of weapon distribution, i.e. some sections of the target area needs more explosives than the rest of the target. For example in ﬁgure 4.8, the section “A” in the target area needs higher density of weapons than the remaining sections of the target. To achieve this non-uniform weapon distribution, the original target area can be divided into several targets as illustrated in the ﬁgure 4.8 and assign the required number of weapons to each target sector as required (see the simulation results in ﬁgure 4.11 and 4.12 for the behavior of the weapon system assigned to two diﬀerent target areas). 4.5 Simulation Results The guided weapon system is simulated for three basic cases, (i) releases height, convergence and formation behavior analysis for ideal conditions, (ii) evaluating the validity of the release height calculation and demonstrating the performance of algorithm for a real world scenario, (iii) and to demonstrate the behavior of the second stage controller in disturbances (shape transition, removal/addition of members). To compare the performance of the real and ideal situations, we present the simulated events for ﬁrst two cases together. First we demonstrate the behavior of the weapon system released by multiple aircrafts and converging into a single target area. For the second event, we selected a situation where weapons launched from a single deployment system moving toward two targets. In both events the released height was calculated theoretically and compared with simulated (both ideal and real scenarios) vertical travel when all the members converge into the circle. For the behavior demonstration under the second stage controller, we present only the motion of the weapons in horizontal directions. In the simulation case studies (except the point generated shape), the shape contours are generated by the mathematical function described in Appendix I. Also the artiﬁcial friction force weighing parameter is selected by kF = 2 mkA1 l(γ) + 1, which enables stable convergence of the whole swarm toward the contour. The mass of the robot (m) is kept constant at 100kg and density of air ρ is considered to be Chapter 4. Application Case Study: Swarming Guided Weapons 63 2800 Y−Coordinate [m] 2600 Height [m] 4000 3000 2000 1000 0 X− Co20001000 or di 0 na −1000 te −2000 [m ] 3000 2000 1000 0 −2000 −1000 ] te [m rdina o Y−Co (a) 3-D view of the motion 2400 2200 2000 1800 1600 1400 1200 500 1000 1500 X−Coordinate [m] (b) Aerial view of the motion Figure 4.9: Motion of Weapon System Aimed at a Single Target - Ideal Conditions constant at 1.814kg/m3 for every simulation case. Further, in all simulations the parameters determining the vertical drag force are as follows; Cd = 0.4, Ar = 1.57m2 . Moreover, in the realistic simulated cases we use following parameters, Cd,h = 0.1, Ar,h = 0.53m2 , a random localization error of 5m (i.e. σ(ηi ) = 5, μ = 0) and acceleration is limited to 2G (19m/s2 ). Remark 4.5.1. In ﬁgures 4.9, 4.10, 4.11, 4.12, 4.13 the red dots represents the position of each weapon when the system switched to the second stage of the controller. The black dots represents the positions of each weapon when reached the target shape (i.e. when contact the target area) while crosses represent the initial positions of the weapons. 4.5.1 Multiple Aircrafts Engaged in a Single Target Here all the weapons are released at 4500m altitude. Considering the target is at 0m altitude, the calculated minimum altitude weapon release is 3167m. In the simulation case studies, the weapons in ideal conditions (Figure 4.9) converged to the desired radius after traveling 757m in vertical direction and in under realistic conditions (Figure 4.10) it takes up to 1584m of vertical travel, which is well below the calculated travel height. Also under the ideal conditions, the weapon system took 2798m for all the weapons to achieve less than 2m/s horizontal speeds and under realistic conditions it took 4289m of vertical travel. In selecting the 2m/s speed limit, based on extensive simulation case studies authors noticed that the motion of the weapons with less than 2m/s does not contribute in spreading inside the shape signiﬁcantly. The following parameters were used in the simulations, kA1 = 0.0025, kA2 = 0.01, kR2 = 1 × 105 , kM = 6 × 106 , a = 3, b = 1, c = 0.5, d = 300 and N = 34. 4.5.2 Single Aircraft Engaged in Multiple Targets All the weapons are released at 4500m altitude. Considering the target is at 0m altitude, the calculated minimum altitude weapon release is 3304m. In the simulation case studies, the weapons in ideal conditions (Figure 4.11) converged to the desired radius after traveling 1055m in vertical direction and in under realistic conditions (Figure 4.12) it takes up to 2183m of vertical travel, which is well below the calculated travel height. Also under the ideal conditions, the weapon system took 3180m for all the weapons to achieve less than 2m/s horizontal speeds and under realistic conditions it took 3467m of vertical travel The parameters used in the simulations are shown in table 4.5.2, while kM is selected as 6 × 106 . In the simulations 34 weapons were directed to shape 1 and 20 were directed to the shape 2. Remark 4.5.2. In above cases, the vertical distances traveled by the weapon system to “fully spread” inside the given contour under ideal conditions are less than the corresponding calculated released height 64 Chapter 4. Application Case Study: Swarming Guided Weapons 2800 2600 Y−Coordinate [m] 4000 Height [m] 2400 3000 2000 1000 2200 2000 1800 1600 0 X− 2000 C 1000 oo 1400 −2000 0 na−1000 te −2000 rdi [m ] 0 2000 ina oord Y−C ] te [m 1200 (a) 3-D view of the motion 500 1000 1500 X−Coordinate [m] (b) Aerial view of the motion Figure 4.10: Motion of Weapon System Aimed at a Single Target - Realworld Conditions Table 4.3: Parameters used for simulations in Figure 4.11 and 4.12 Shape 1 2 a 3 5 b 1 1 c 0.5 0.5 d 250 100 kA1 0.0025 0.0005 kA2 0.01 0.01 kR2 2 × 104 2 × 104 −1500 X−Coordinate [m] −1000 Height [m] 5000 4000 3000 2000 1000 0 2000 X− Co −2000 ord 0 ina te−2000 [m] 2000 oo Y−C (a) 3-D view of the motion m] te [ rdina 0 −500 0 500 1000 1500 1500 2000 2500 Y−Coordinate [m] (b) Aerial view of the motion Figure 4.11: Motion of Weapon System Aimed at a Multiple Targets - Ideal Conditions for convergence. Under realistic conditions the vertical distances traveled for achieving the same state are slightly greater than the calculated release heights. 4.5.3 Point Generated Shapes In real-world military missions, it is not always possible to generate the required target shape by a mathematical function. Instead the shape has to be generated by a series of points (i.e. deﬁning coordinate points to generate the shape contour). With this method, any arbitrary shape can be generated for the Chapter 4. Application Case Study: Swarming Guided Weapons 65 −1500 X−Coordinate [m] −1000 Height [m] 5000 4000 3000 2000 1000 −500 0 500 1000 0 X−2000 Co ord −2000 0 0 ina 2000 te −2000 [m] ate ordin 1500 [m] 1500 o Y−C 2000 2500 Y−Coordinate [m] (a) 3-D view of the motion (b) Aerial view of the motion Figure 4.12: Motion of Weapon System Aimed at a Multiple Targets - Realworld Conditions 2500 9000 8000 2000 Y−Coordinate [m] Height [m] 7000 6000 5000 4000 3000 2000 1000 1500 1000 X− 500 Co 0 ord ] [m te ina 2000 1500 1000 500 −2000 0 2000 ] te [m ordina Y−Co (a) 3-D view of the motion 0 0 500 1000 1500 2000 2500 X−Coordinate [m] (b) Aerial view of the motion Figure 4.13: Motion of the weapon system into a point generated arbitrary shape. weapon control algorithm. In this case study, we present a formation of 65 weapons into a shape deﬁned using 234 points (see ﬁgure 4.13). Here, the center of the circle for stage switching is located closer to the center of the contour and the radius is manually selected to reach the contour line. 4.5.4 Shape Transitions Here we demonstrate the behavior of the weapon system, when subjected to a sudden change in the contour’s shape. This kind of shape transitions are important in real world applications, specially when targeting changing and moving targets, such as convoys, gathering of vehicles etc. From the computer simulation results shown in ﬁgure 4.14, the weapon system initially in a heptagonal formation (represented in red) is disturbed by a transition of the contour shape. The ﬁgure illustrates the motion paths and ﬁnal positions of the weapon system forming into the new triangular shape. It is clear from this simulation, the weapons eﬀectively maneuver themselves to form the new shape and redistribute within that shape. 66 Chapter 4. Application Case Study: Swarming Guided Weapons Height [m] 8000 7800 7600 7400 7200 −2000 Y− Co −2200 ord −2400 ina te −2600 [m ] 1200 800 X i ord o −C m] e[ nat 1000 Figure 4.14: Behavior of the weapons in shape transitions. Initial weapon conﬁguration at 8000m was disturbed by shape transition. Weapon positions and shape in red color represents the initial conditions and the ﬁnal conditions are represented in black color. The simulation used the parameters in table 4.4. Table 4.4: Parameters used to generate Figure 4.14 Case Initial Final 4.5.5 a 7 3 b 1 1 c 1 0.8 d 45 130 kA2 4 × 10−3 4 × 10−3 kR2 5.2 × 103 5.2 × 103 kM 5.9 × 105 5.9 × 105 Addition/Removal of Agents Ability to reconﬁgure the weapon’s horizontal positions, when subjected to addition or removal of weapons demonstrate signiﬁcant importance in achieving eﬀective distribution. In most deployments targeting military establishments, the weapons have high probability in caught up with enemy ﬁre. In such circumstances, redistribution of remaining weapons to cover the target area is highly advantageous in delivering even destruction to the target area. Also, some times inclusion of additional weapons is also a possible scenario, when the existing number of weapons become insuﬃcient for the target. With this simulation case study, we present the behavior of the weapon system (operating in second stage of the controller) in removal (Figure 4.15(a)) and addition (Figure 4.15(b)) of the weapons. For the simulations we used the parameters listed in table 4.5. Table 4.5: Parameters used to generate Figure 4.15 Case Addition Removal a 6 6 b 1 1 c 0.5 0.5 d 55 55 kA2 4 × 10−3 4 × 10−3 kR2 6.2 × 103 7 × 103 kM 5 × 105 9 × 105 Chapter 4. Application Case Study: Swarming Guided Weapons 67 8000 Height [m] Height [m] 8000 7500 7000 6500 6000 7000 6500 6000 5500 5500 −2100 −2200 −2300 −2400 −2500 Y− 7500 1200 Co ord ina te [m ] 1000 800 a rdin o Co X− m] te [ (a) Removal of Members in the Flight 600 −2000 X− Co 800 1000 ord ina 1200 te [m ] −2200 −2600 ate [m] in ord −2400 Co Y− (b) Addition of New Members in the Flight Figure 4.15: Behavior of the Weapon System when disturbed while in Flight. In sub ﬁgure (a), the weapons removed from the group at 8000m altitude are represented by red crosses. In sub ﬁgure (b) Initial conﬁguration at 8000m was disturbed by new additions to the group. The paths and positions of new additions are shown in red color. 4.6 Summary In this chapter we have presented an approach to control a group of guided weapons to be distributed inside a given geographical shape, speciﬁed by either a mathematical function or series of points. The control algorithm uses artiﬁcial formation forces to attract and guide the weapons into the shape. Artiﬁcial inter-weapon repulsion forces were used to distribute the weapons evenly inside the shape while eliminating collisions among weapons. The two tier controller of the proposed weapon system ensures stable convergence of the weapons into the desired shape. The weapon system was analysed for stability, time of convergence, and conditions for cohesive behavior. Moreover, an important result on the release height of the weapon system was obtained which ensures that all the weapons are converged into the desired geographical boundary at the time of impact. Computer simulations were used to verify the theoretical assertions and the behavior of the weapons when subjected to sudden change of target shape, loss/addition of weapons into the group etc. Also a modiﬁed model compensating for the size of weapons, thrust limitations and errors in localization which closely resemble real-world scenarios, was introduced and computer simulations were used to conﬁrm the behavior. Chapter 5 Communication and Power Saving Schemes for the Swarm Swarm robotics and wireless sensor networks, can sometimes be considered as a single research discipline. In many cases, the algorithms developed for ad-hoc connected wireless sensor networks can be directly used for communications in swarm robotics, which share similarities such as limited relative mobility, ad-hoc connectivity, utilization of limited energy reserves, small data packet size, fast communication etc,. In this chapter we introduce two communication protocols that are speciﬁcally designed to save the limited energy reserves in energy critical wireless communication links while achieving the goal of eﬀective communication. The communication algorithms introduced in this chapter are primarily focused on wireless sensor networks domain, however they can be adopted in multiple robot coordination domain without any modiﬁcations. The concluding chapter (chapter 6) of this dissertation illustrates such scenario. In the robotic swarm introduced in this dissertation, the knowledge of the positions of the other members is critical for accurate pattern generation. Specially in the two-stage controller introduced in the chapter 4, the instantaneous knowledge of the other members of the swarm is utmost important in switching to the second stage of the controller. In the section 5.1, we introduce an all-to-all communication algorithm to be used for communication within the swarm. The proposed architecture satisﬁes the instantaneous knowledge of positions of every member in the swarm as well as uses the minimum transmission power to convey the message. In the section 5.2 we introduce an algorithm for controlling the transmission powers of remote wireless agents deployed in a mobile data collector based data gathering scenario, which has many potential applications in the swarm robotic domain. 5.1 Fully-Connected mesh network for eﬀective communication 1 Recent past has witnessed a growing popularity in the multi-cast networking technologies, which have added advantages in the modern communication needs such as internet based multimedia services (news, distant learning etc), multimedia conferencing facilities for computers and mobile phones[150, 151]. In multi-casting, the broadcasting of a single data packet to the network by the node dramatically improves the bandwidth usage in comparison to the unicast networks (one-to-one networks). In addition to the multimedia communication; distributed computing, parallel processing , swarm robotics , and wireless sensor networks where each node have some information to share with the other nodes have distinct advantages in employing all-to-all networks (multi-casting) [152]. All-to-all communications, proposed by Yang and Wang can be classiﬁed as: all-to-all broadcasting and all-to-all personalized exchange depending on the nature of the communication[153]. In the former case, the information (data packet) originating from a single node is propagated through the entire 1 Please note that the material presented in this section is based on the conference paper: S.W. Ekanayake, P. N. Pathirana, B. F. Rolfe, and M. Palanaswami, “Energy eﬃcient, fully-connected mesh networks for high speed applications,” in IEEE Vehicular Technology Conference, VTC2008, Singapore, 2008 69 70 Chapter 5. Communication and Power Saving Schemes ... network and in the latter case every node has distinct information to share with every other node in the network. Routing algorithms for both network types have been extensively researched in the past [154, 155, 156, 157, 158]. However, these routing algorithms were based on multi-hopping mesh and torus based network architectures and involve routing tree generation, forwarding link assignments, subnetwork creation etc. They also have many practical diﬃculties in applying to all-to-all ad-hoc networks [159, 160, 161]. In modern distributed / parallel processing applications, the network essentially consists of time varying nodes (location changes and addition / removal of nodes), which cause changes in the mesh / torus at each instance of architectural change. Moreover, those multi-hopping all-to-all networks comprises of hopping (routing) delays and increased network congestion with increasing network traﬃc, resulting in loss of vital information. In this section, we consider a situation where an ad-hoc connected multiple-node wireless network requiring instantaneous all-to-all personalized communication, which is distributed within a close range such that the single-hop communication can be achieved between every node. The communication scheme introduced here enables all-to-all networking of the nodes without forwarding tree generation based on the spatial conﬁguration of the nodes, i.e. node mobility, addition / removal of nodes etc. The proposed network uses CDMA based communication architecture which enables the entire network to communicate simultaneously. Moreover, we derive the capacity of the network in-terms of the number of nodes in the network and introduce a power control algorithm which ensures that all the nodes are transmitting at the minimum possible transmission power while maintaining the connectivity of the entire network ensuring interference free communication. The rest of this section is organized as follows. In the sub-section 5.1.1, we discuss the related work in the CDMA power control and power control aspects in ad-hoc networks. Then in the problem formulation (sub-section 5.1.2), we introduce the network architecture and the communication model used in this research. Furthermore, we derive the capacity of the network for QoS guaranteed communication links based on the CIR constraint. Then the Power Control (PC) algorithm is introduced and the control parameters are analyzed in the sub-section 5.1.3. Also we use computer simulations to illustrate the behavior of the system operating under both ideal and real-world conditions. 5.1.1 Power Control in Wireless Networks CDMA and Power Control in Cellular Systems Among the multiple access schemes in wireless communications, CDMA has become the most promising technology that can satisfy most aspects in modern communication networks, such as higher speeds, larger client base and QoS guaranteed communication. Although CDMA started service in cellular communications in late 90’s, the concept was originally introduced by Claude Shannon and Robert Pierce in 1949 [162], and then extended by DeRosa-Rogoﬀ, Price & Green and Magnuiki [163, 164]. The early developments of this technology were primarily focused on the military and navigation applications (satellite communication etc). As the ﬁrst civilian application, a narrow-band spread spectrum CDMA scheme for cellular communication was ﬁrst proposed by Cooper and Nettleton in 1978 [165] and then developed to the IS-95 and CDMA2000 standards which are used in modern CDMA wireless communications [166]. Maintaining the Carrier-to-Interference Ratio (CIR), alternatively referred as the co-channel interference, at a desirable level is the main aspect of power control in CDMA networks. In CIR balancing, the transmission powers of every user device is controlled such that it ensures the co-channel interference of each link guarantees QoS reception. CIR balancing in a cellular system has two aspects: intra-cell CIR balancing and inter-cell CIR balancing. In intra-cell CIR balancing the user devices control the transmission power such that it provides a constant received power at the base station [167] to avoid near-far problem. This method is currently in practice with CDMA standards such as IS-95 and CDMA 2000 [145]. Inter-cell CIR balancing received widespread attention among the academic community after the problem reformulation by Zander et al. in [168]. This work was further investigated by Grandhi et al. [169, 170, 171] and the Distributed Power Control (DPC) scheme proposed by Foschini and Miljanic [172] has become a standard benchmark due to its academic and practical signiﬁcance (see [173, 174, 175] for Chapter 5. Communication and Power Saving Schemes ... 71 ith Node Gij Gkj jth kth Node Node Figure 5.1: An all-to-all network consisting of six nodes. further improvements), which was later adopted into wireless communication standards [176]. Power Control Aspects in Ad-hoc Networks Many wireless ad-hoc networks, such as sensor networks and military communication networks, are inherently associated with restrictions in power consumption mainly due to the limited energy resources such as batteries. Therefore, unlike in cellular communications, the power control in wireless ad-hoc networks are basically focused on energy conservation. Many power conservation techniques introduced for such networks can be found in the past research literature[177, 178, 179, 180, 181, 182, 183, 184]. Among them routing optimization [177, 178, 179, 180] and transmission power control [181, 182, 183] are the widely researched areas. However as opposed to the above, diﬀerent eﬀective methods such as sleep and wakeup procedures implemented in the hardware layer [184], were also proposed. 5.1.2 Problem Formulation Now we formally introduce the power control problem together with the associated network architecture, control constraints and network capacity. Network Architecture Consider a single hop all-to-all wireless network (Ω) in which N nodes communicate with each other simultaneously (see Figure 5.1) using spread-spectrum multiple access protocol (such as CDMA). In this network, the nodes are broadcasting the data continuously, rather than maintaining node-to-node communication links. The broadcast data from a particular node, which is uniquely coded, can be accessed by every other node in the network. The network model assumes followings; • Nodes have instantaneous and error free Received Signal Strength (RSS) measurement capabilities. • The measurements are immediately included in to the broadcast data, which will be used for the PC process. • Link gain variations are negligible compared with the communication and the data processing time. • All the nodes in the network are identical in performance (homogeneous). In the controller analysis, the above assumptions are used in order to reduce the system complexity; however in later sections we relax these assumptions and present the controller behavior with erroneous measurements, non-homogeneous node properties, and link gain variations which resemble a real-world scenario. 72 Chapter 5. Communication and Power Saving Schemes ... Control Constraints In order to achieve QoS guaranteed communication in every link, two conditions must be satisﬁed simultaneously; CIR constraint and the connectivity constraint. CIR Constraint : Any node j in the network can receive the signal transmitted from any other node i, correctly, if the CIR measured at the j th node (γij ) is greater than the threshold CIR value γt . Then the CIR constraint can be deﬁned as; γij = Pi Gij N ≥ γt , ∀i, k, j ∈ Ω (5.1.1) Pk Gkj + η k=i,k=j where Pi is the transmission power levels of the ith node. In the above expression, Gij and Gkj are the link gains between i, j and k, j nodes respectively. Here the η represents the noise power (thermal noise) in the communication link and this is assumed to be constant for the geographical area (see [173, 172]). Connectivity Constraint : To receive a signal from any node i, the received power level of the signal measured at the j th node (Rij ) must be greater than the receiver threshold Rmin , which is the sensitivity of the receiver hardware. In this study the threshold received power is deﬁned such that, the reception is not aﬀected by the thermal noise of the band. Then the received power condition can be deﬁned as (considering Rij = Pi Gij + η); Pi Gij + η ≥ Rmin , ∀i, , j ∈ Ω . (5.1.2) Capacity and spatial limitations In order to satisfy the above constraints, the all-to-all network has certain limitations in the spatial conﬁguration and network capacity. This section derives the network capacity which ensure QoS guaranteed communication, and the relationships between the receiver sensitivity and the spatial conﬁguration (link gains) to maintain reliable links. From the connectivity constraint we get, min (Pi Gij + η) ≥ Rmin , (5.1.3) i,j∈Ω which provides a condition that the network should satisfy at all the times for the power control algorithm to perform the desired action. Moreover, the network always satisﬁes the connectivity constraint (“connectivity guaranteed” networks) if: Pmin Gmin ≥ Rmin − η; (5.1.4) Pmax Gmin ≥ Rmin − η. (5.1.5) and the network is “feasible” if: Here, Pmin and Pmax refers to the minimum and maximum transmission power levels of the nodes respectively, and Gmin is the minimum link gain between any two nodes in the network. Above, the term “feasible” means that the network can achieve the connectivity constraint. From the CIR constraint (equation (5.1.1)); min (Pi Gij ) i,j∈Ω 1 + γt γt ⎛ ≥ max ⎝ k,j∈Ω N ⎞ Pk Gkj + η ⎠ , k=j thus for “connectivity guaranteed” network: 1 + γt ≥ (N − 1)Pmax Gmax + η, Pmin Gmin γt (5.1.6) Chapter 5. Communication and Power Saving Schemes ... resulting, N ≤1+ 1 + γt γt Pmin Gmin Pmax Gmax − 73 η Pmax Gmax . (5.1.7) For the “feasible” network: Pmax Gmin limiting the capacity as, N ≤1+ 1 + γt γt 1 + γt γt ≥ (N − 1)Pmax Gmax + η, Gmin Gmax − η Pmax Gmax . (5.1.8) Deﬁnition 5.1.1. Limited Capacity Network : A multi-casting network satisfying the equation (5.1.8) on the number of nodes is deﬁned as a Limited Capacity Network. Remark 5.1.1. In above derivations, the network capacity is determined in terms of the number of nodes connected (N ) at an instance and this number is dependent on the target CIR (γt ). In spread spectrum networks, γt is selected to maintain the desired network quality, bandwidth and the data transfer speed [167]. Thus limiting the number of nodes to N ensures that the desired communication capacities/qualities are preserved in the network. Remark 5.1.2. In limited capacity networks, the range of link gains in the desired geographical area (Gij ∈ [Gmin , Gmax ]) is a decisive factor on the number of nodes. However, this enables us to accurately select the number of nodes to be deployed in a particular region, knowing the range of link gain at that region. Remark 5.1.3. In limited capacity networks, the maximum number of nodes (Nmax ) is deﬁned such that the networks always satisfy the CIR constraints without directly depending on the spatial distribution of the nodes. However, this does not mean that a network with number of nodes N > Nmax in the same geographical area (not necessarily in the same conﬁguration) does not satisfy the CIR constraints. Intended Controller Behavior for Energy Conservation In this power control problem, we consider an ad-hoc network satisfying “Limited Capacity” and “feasible” conditions. The problem considered here is to maintain all-to-all communication links in such networks, while minimizing the network power consumption via transmission power control. The proposed power control algorithm is focused on maintaining minimum requirements for satisfying the connectivity constraints, which automatically satisﬁes the CIR constraint in a Limited Capacity network. 5.1.3 Iterative Controller In this section, we present a transmission power control scheme (see ﬁgure 5.2) to maintain the received powers at the desired value that satisfy the connectivity of the network, and derive the tolerance limit for selecting the target received power. The transmission power of the ith node (Pi ) is determined by, P˙ i = a(ei − Rt ), (5.1.9) N here a < 0 is a constant, ei is the average received power at the other nodes, i.e ei = (Pi Gij + η) j=i N −1 Rt is the target received power which satisfy the connectivity constraint for all the nodes. , and Remark 5.1.4. In this power control algorithm, we assume that the nodes are transmitting at the maximum transmission power at time zero (at the initialization of the algorithm). 74 Chapter 5. Communication and Power Saving Schemes ... jth Node 6 Pj(t-1) + (n-1) a - + + Pj(t) Rt ++ K ++ K ++ K P1(t) Pi(t) Pn(t) 1st Node ith Node nth Node Figure 5.2: Block diagram representation of the controller of the j th node 5.1.4 Convergence of the controller From the deﬁnition we have, ei = Pi Ai + η and thus e˙ i = P˙i Ai , where Ai = gain” for the ith node. With this, the controller function can be reformulated as: $N j=i Gij N −1 is the “average link e˙ i = aAi (ei − Rt ) , From the above expression it is evident that the control variable ei converges to Rt , if aAi < 1. Remark 5.1.5. Since Gi,j < 0, ∀i, j and selecting a < 1 always satisﬁes the aAi < 1 condition for the convergence. Satisfying Connectivity for Every Node The convergence of the above controller describes the trajectory of the average received power, however, it does not say anything about the trajectories of the RSS in each link or their connectivity. In this section, we obtain a relationship between link gains, sensitivity of the receiver hardware and the target RSS value, which can be used to determine the tolerance limit when selecting Rt . This relationship is formally introduced in the following proposition. Proposition 5.1.1. In an all-to-all network using the power controller described by (5.1.9) and deployed in a geographical area having link gains within a known range, i.e. Gij ∈ [Gmin , Gmax ], the connectivity Rm + η(X − 1) , where constraint is always satisﬁed if the threshold value for the power controller, Rt ≥ X Gij . X = min i,j∈Ω Ai Proof. Let the error between the average RSS and the RSS of the node j, eij = Rij − ei = Pi (Gij − Ai ) and the time derivative; e˙ ij = P˙i (Gij − Ai ) . Chapter 5. Communication and Power Saving Schemes ... 75 Then using the control function (5.1.9) we have, Gij −1 . (5.1.10) e˙ ij = aAi eij − (Rt − η) Ai Gij − 1 , if the conditions for the conAbove expression implies that eij converges toward (Rt − η) Ai vergence of ei are satisﬁed. Since the above statement is valid for any node i, j in the network, we can determine the lower bound of eij as; Gij −1 . (5.1.11) min (eij ) ≤ (Rt − η) min i,j∈Ω i,j∈Ω Ai For an all-to-all ad-hoc network deployed in the geographical area with Gij ∈ [Gmin , Gmax ], we have; Gij (N − 1) Gmin . (5.1.12) = min i,j∈Ω Ai Gmin + (N − 2) Gmax Then, the connectivity condition for any link i, j is satisﬁed if, Rt + min (eij ) ≥ Rmin , i,j∈Ω i.e. Rt ≥ Rm + η(X − 1) X where, X = min i,j∈Ω Gij Ai (5.1.13) which proves the assertion. Simulation Results Power control algorithm : In this section a simulation case study is presented which illustrates the behavior of the system in an ideal situation described in the problem formulation section. The following parameters were selected for the simulation, Pi ∈ [0.1, 3], Gij ∈ [0.3, 0.6], Rmin = 0.1, γmin = 0.1, η = 0.05, and N = 4. With the selected parameters, the feasible condition (Rmin≤ 0.3 × 3 = 0.9) and the “Limited Capacity” 0.3 0.05 1.1 − = 6.417 are satisﬁed. The target received power (Rt ) network condition N ≤ 1 + 0.1 0.6 0.6 0.1 + 0.05(0.6 − 1) = 0.1333. The simulation results are is selected using equation (13) as: Rt = 0.2 > 0.6 shown in Figure 5.3. It is evident from the simulation ﬁgures that the controller converges to the minimum transmission power that satisﬁes all the constraints described in the previous section. Network limitations : In this section we evaluate the theoretical assertions on the network limitations. In ﬁgure 5.4, the variation of CIR with increasing number of nodes is presented. In this ﬁgure, minimum and maximum CIR values for each node count are obtained by executing the simulation for 20 times with random selection of gain matrix ,Gij ∈ [0.3, 0.6] and all other values are kept as in the previous case. It can be seen that the CIR range drops below the threshold value of 0.1 just after the node count exceeds 7 (the calculated maximum node count N < 6.417). Controller behavior in a real-world scenario : In this section, we illustrate the behavior of the proposed control scheme in the presence of real-world communication properties. Here the network is considered to have hertogeneous nodes, erroneous measurements and link gain variations (due to motion and other mobile obstacles). 76 Chapter 5. Communication and Power Saving Schemes ... Transmission power of nodes 3 2.5 2 1.5 1 0.5 0 0 10 20 30 40 50 Time Step (a) Transmitted Powers 0.7 CIR at each node 0.6 0.5 0.4 0.3 0.2 γ t 0.1 0 5 10 15 20 25 30 35 40 45 50 40 45 50 Time Step (b) CIR of each link RSS at each node 1.6 1.4 1.2 R 1 R t min 0.8 0.6 0.4 0.2 0 5 10 15 20 25 30 35 Time Step (c) RSSI of each link Figure 5.3: Eﬀect of the transmission power control algorithm The measurement error at j th node is modeled as a normal distribution νj ∈ [0, σν2 ], and the link gain ˆ ij = Gij 10(X/10) , where X is the dB attenuation due to shadowing eﬀect and modelled as is modelled as G 2 ). Then the received power measurement can be modeled a Gaussian variable in the form of X N (0, σX as, ˆ ij + η 10νj /10 . (5.1.14) Rij = Pi G The hetrageneous properties are modelled as diﬀerences in power transmission and power measurements, which are common in real-world communication equipments. The actual transmission power of the ith node is modelled as Pˆi = αi Pi , where αi ∈ (αmin , 1) determines the power of the transmitter and is unique to each node. Similarly, the received power measurement performance factor βi ∈ (βmin , 1) determines ˆ ij = βi Rij . the actual measured received power R In the simulation results shown in ﬁgure 5.5, we consider σX = 2, σν = 0.4, αmin = 0.8 and βmin = 0.7 (αi and βi values are randomly assigned for each node). According to the simulation results, the power control algorithm performs well in the presence of real-world limitations, maintaining the CIR of every link above the target (threshold CIR) as well as RSS of every link above the minimum RSS. Chapter 5. Communication and Power Saving Schemes ... 77 Max CIR Min CIR γ 1.2 Min/Max CIR Levels t 1 0.8 0.6 0.4 0.2 0 2 4 6 8 10 12 14 16 18 20 Number of Nodes Figure 5.4: Behavior of CIR with number of nodes in the mesh. 5.2 5.2.1 A simple power control algorithm for mobile data collector based remote data gathering scenario Motivation and background 2 In most low end networking devices CIR can not be directly measured, instead received power (in dBm) and Link Quality measurements can be obtained directly from the hardware. This raise the need of power control algorithms which do not entirely depending on CIR measurements, but depends on rather measurable parameters. In this study we derive the optimum value for co-channel interference measured at a base station, and introduce two power control algorithms to implement in user devices which can alter the transmission power to obtain the required CIR. In the proposed schemes we make use of Received Signal Strength Indication (RSSI) measurements to achieve the desired CIR at the base station. In the next section (section 5.2.2) we introduce the problem in a formal manner, and in section 5.2.3 we justify our assumptions with experimental reasoning. Then in section 5.2.4 we introduce the controller and perform analysis for the convergence. 5.2.2 Problem formulation In this section we introduce the basic assumptions and models which will be used in the power control scheme. In this study we use the term “Server” to denote the base station node which communicate with all the “Clients” within the range. Here “Client” refers to the sensory node/ user device which is connected to the base station. The notation in Table 5.1 is used throughout the paper. Consider a wireless network with n clients connected to a single base station in a typical environment consisting of uncertainties in RF propagation due to shadowing, multi path propagation etc. The clients communicate with the server continuously using a common frequency band (as in CDMA). The server has a limit of nmax clients connected with it at an instant, and has a receive threshold of Rmin (dBm) which is depending on the sensitivity of the receiver hardware. Also we assume that the communication network is not interfered by any other RF network in the domain of the base station (or “cell” in the cellular networking terminology). Throughout this paper, we assume that the server and the client maintain a continuous communication link, in which the server sends an acknowledgment signal back to the client for each data packet received (similar to [173]). This signal contains the RSSI of the received packet and the transmission power (if not transmitting at a ﬁxed power) of the acknowledgment signal, which will be used in the PC algorithm. Also the communication hardware (server and client) have the capability 2 Please note that the material presented in this section is based on the conference paper: S.W. Ekanayake, P. N. Pathirana, andM. Palanaswami, “Maintaining optimal co-channel interference for power eﬃcient wireless communication,” in ISSNIP conference 2007, Melbourne, Australia, 2007 78 Chapter 5. Communication and Power Saving Schemes ... Transmission power of nodes 3 2.5 2 1.5 1 0.5 0 0 10 20 30 40 50 Time Step (a) Transmitted Powers 1.8 CIR at each node 1.6 1.4 1.2 1 0.8 0.6 0.4 0.2 0 5 10 15 20 25 30 35 40 45 50 40 45 50 Time Step (b) CIR of each link 3.5 RSS at each node 3 2.5 2 1.5 1 0.5 0 5 10 15 20 25 30 35 Time Step (c) RSSI of each link Figure 5.5: Eﬀect of the transmission power control algorithm - Real world scenario Table 5.1: Notation P Ti P Tm Rm i Rim Rm 0 Ri0 Transmission power of ith node. (dBm) Transmission power of server node. (dBm) Received power measured at client i, transmitted by server node. (dBm) Received power measured at server node, transmitted by node i. (dBm) Received power measured at reference distance (d0 ), transmitted by server node. (dBm) Received power measured at reference distance (d0 ), transmitted by client node i. (dBm) to measure the RSSI of each data packet. Chapter 5. Communication and Power Saving Schemes ... 79 Figure 5.6: Modeling of 2D Multi-path propagation inside an enclosed environment, the ﬁgure presents few possible paths of multi-path propagation. 5.2.3 Path loss model We use the following path loss models for communication between the client node and the server node, d i i Rm = R0 − 10η log10 (5.2.1) + S im d0 and Rm i = Rm 0 − 10η log10 d d0 + S mi , (5.2.2) here term η refers to the path attenuation factor, which is a constant depending on the propagation media. In above expressions, S im and S mi refer to the combined eﬀects due to shadow fading, multi-path propagation and any other fading eﬀect occur from environmental factors such as presence of people, animals etc. For line-of-sight communication in outdoor environments, specially long distance, the propagation of RF (Radio Frequency) waves can be approximated using free-space path loss model. This is possible as multi-path propagation and shadow fading eﬀects do not become signiﬁcant in such environments. Whereas, for wireless networks in indoor environments, the propagation is harder to predict due to presence of multi-path eﬀects. Many researchers have studied the phenomenon of multi path propagation and proposed RSSI models for indoor environments with the presence of obstacles [185, 186, 187, 188, 189]. Applicability of those models for mobile nodes is debatable due to dynamic nature of environments and thus the model. Further, the experimental studies done by Lin et. al. in [183] claims that the RSSI value between two nodes in the line of sight have signiﬁcant changes over the course of the day, thus location based mathematical models become inapplicable. Ray-tracing concept for RF propagation, on the other hand, become a handy tool for predicting RSSI variation in an indoor environment [190, 191, 192]. Here, the radio waves are considered to follow the properties similar to visual light propagation in the presence of transparent obstacles. The eﬀectiveness of Ray-Tracing method for RF waves increases with high frequencies. This is due to reduced scattering eﬀects in shorter wave lengths. We use ray-tracing concept to make an assumption on the S xx terms in equation (5.2.1) and (5.2.2), as follows; S im (k) = S mi (k), ∀i = 1 . . . n where k represents a time step in discrete time. As in ﬁgure 5.6, there exists more than one path for receiving the signal from a RF source to a sink, and the overall S term consists combination of all the multi-path propagation terms. With the assumption above, we claim that if the sink and source positions in the ﬁgure 5.6 was interchanged then the only diﬀerence with the previous case is that the direction of propagation. That is all the multi-path links remain the same except the direction, thus results the same S eﬀect at the sink in the new conﬁguration. The following experimental results justiﬁes our assumption. 80 Chapter 5. Communication and Power Saving Schemes ... Figure 5.7: Experimental setup for the ray tracing experiment - In this ﬁgure only four receiver nodes are shown however in the real experiment we used ﬁve receiver nodes and performed the experiment in several environments representing diﬀerent disturbance and reﬂection levels. Table 5.2: Expected values of measurements Node 1 Node 2 Node 3 Node 4 Parameter E Rim / (dBm) ) / (dBm) E (R m i i E R0 / (dBm) E (R m 0 ) / (dBm) E (S im − S mi ) / (dBm) Node 5 -62.56 -65.96 -62.20 -62 -64.01 -62.00 -64.00 -61.99 -61.94 -66.00 -39.28 -40.65 -39.00 -41.00 -37.01 -39.00 0.29 -39.00 0.31 -38.08 -0.72 -41.00 0.06 -39.00 0.00 Basis for Ray-Tracing Assumption In this experiment, four nodes (stationary nodes) were placed in an indoor environment and a mobile node communicating with them was randomly moved in the same environment (see Figure 5.7). The received powers at each stationary node and the received power of the corresponding acknowledgment signal at mobile node were recorded. All the nodes are transmitted in a ﬁxed transmission power and i the corresponding Rm 0 and R0 values were measured with d0 = 10cm (this was conducted in a large open space to minimize the eﬀect of multi-path propagation). Then the expected value of the S im − S mi can be written as follows. m ) + E ( R ) − E Ri0 E (S im − S mi ) = E Rim − E (Rm i 0 The statistical data of the measurements and calculated S im − S mi are presented in Table 5.2.3. Chapter 5. Communication and Power Saving Schemes ... 81 From the experimental data it is evident that the S im − S mi term is zero. In this experiment, even though all the transmitters are transmitting with the same power, we used the measured received powers m at a reference distance rather than assuming Rm 0 = Ri in order to eliminate the eﬀect of antenna gains. Remark 5.2.1. In environments with such uncertainties (e.g. indoor, urban etc) ray-tracing concept can be used to predict the radio wave propagation [190, 191]. Here, the radio waves are considered to follow the properties similar to visual light propagation in the presence of transparent obstacles. 5.2.4 Power control analysis Optimum Carrier-to-Interference Ratio CDMA base stations have a minimum CIR value (γmin ) which guarantee QoS reception. In CIR based power control algorithms such as [172, 173, 174] etc the controller is trying to maintain the CIR at a ﬁxed value γf ≥ γmin . In this paper, we introduce a dynamic target CIR value (γ t ≥ γmin ) which is the optimal CIR for the number of clients connected with the server at that instance. The CIR, measured at the server, of the communication with the ith client (γi ) can be deﬁned as follows, Ri n γi = (5.2.3) Rj j=1,j=i where Ri denotes the received power measured at the server, transmitted by the ith client in “Watts”. Note that the Ri includes the random noise of the measurements as well. The server is said to have a good communication with the ith sensor, if the γi is greater than the threshold value γ t . Then the above can be expressed in the following form (as in [168]), n Ri ≥ γt. (5.2.4) Rj − Ri j=1 The vector representation of the above is, 1 + γt γt R ≥ 1n R , (5.2.5) where 1n is the unity matrix and [R]i = Ri . As proposed by Zander in [168] we can derive the optimal γ t value as follows (see Remark 1), 1 , ∀n < nmax , (5.2.6) γt = (n − 1) which results, Ri = Rt , ∀i = 1 . . . n, i.e. the received power values of the signals from every client, measured at the server should be equal. Here Rt is the target received power. This reduces the CIR balancing problem to a simple power control problem as presented in the next section. Remark 5.2.2. Using the Perron-Froebenius theorem (see [108]), the largest real eigenvalue of the matrix 1n can be found as n. Remark 5.2.3. Selecting Rt = Rmin results in maintaining the CIR at the optimal value of gaining the maximum energy saving in the network. 1 while (n − 1) 82 Chapter 5. Communication and Power Saving Schemes ... Transmission Power Control In this section, we propose a power control scheme to maintain the variable CIR presented in the section 5.2.4. Since we proved that maintaining a constant received power at the base station satisﬁes the optimal CIR condition, the ultimate target of the power control algorithm is to maintain Rim at Rt . Iterative Controller The iterative power control algorithm is proposed as follows; T P˙ i = f Rt − Rim . (5.2.7) Here the f (·) is deﬁned as any function satisfying the Lipschitz condition, f (a − b) ≤ k1 a − b (5.2.8) where k1 ∈ [0, 1] is the Lipschitz constant for the function f (·). Proposition 5.2.1. The controller converges the Rim , starting from any arbitrary value, to Rt , if the transceiver gains remain constant. Proof. From the path loss model between the client (5.2.1) and the server (5.2.2) nodes, we have Rim = P Ti − P Tm + Rm i and since P Tm is a constant in our problem, the received power at the client node remains a constant. Then the controller becomes, % & T P˙ i = f Rt − P Ti + P Tm − Rm (5.2.9) i resulting, % & T P˙ i = f C − P Ti + υi , (5.2.10) ˆ i is a constant for the time interval. Here the υi is the random noise in the Rm where C = Rt + P Tm − R i , % & m T m T ˆ ˙ i.e. Ri = Ri + υi . Let p = C − P i , then p˙ = −P i . The equation (5.2.10) can then be written in the vector form as, p˙ = −f(p + υ) = f(−p − υ) (5.2.11) m where [p]i = P Ti , [υ]i = υi and f : n → n , i.e. f(a) = [f (a1 ) . . . f (an )]T , a = [a1 . . . an ]T ∈ n and f(a) = 0 if a = 0, thus the equilibrium point is the desired transmit power in (5.2.7) giving the optimal CIR in (5.2.6). Then as in [173], selecting a = −pa − υ and b = −pb − υ yields, f(pa ) − f(pb ) ≤ k1 (pa − pb ). (5.2.12) Since the above expression satisﬁes the Lipschitz conditions the system converges toward the desired power vector. (see [173] and references there) The numerical simulation results presented in Figure 5.8 shows the behavior of two controller functions; (1) A linear controller (fL ), and (2) A sigmoid based controller (fS ), deﬁned as, fL (a) = 0.3 ∗ a, fS (a) = 2 −0.5 + 1 1 + exp(−a) Remark 5.2.4. Lipschitz constants of the fL (·) is 0.3 and that of fS (·) is 0.5 (see [173]) thus the above control functions satisfy the condition in (5.2.8) and hence agree with the theoretical proof for convergence. Chapter 5. Communication and Power Saving Schemes ... 83 Control Value Magnitude 55 50 45 40 35 30 25 20 15 Linear Controller Sigmoid Controller 10 5 10 20 30 40 50 60 70 Time Steps Figure 5.8: Numerical results showing the convergence of the controllers. Here C = 50 and p(0) = 10 Rt + Controller Server Node Transmitter - Two way communication between the server and the client nodes Client Node Received power feed back link (Rim) (a) Centralized Implementation of the controller C + Controller - Server Node Transmitter Two way communication between the server and the client nodes PTi Client Node (b) Decentralized Implementation of the controller Figure 5.9: Controller Conﬁgurations Special Case for Dynamic Environments - “Direct Method” In the above discussion, we proved that the power control algorithm converges to the desired CIR within a ﬁnite time, however the algorithm needs super-fast convergence for dynamic environments in which the S xx terms change rapidly. Due to the negligible time taken for two consecutive communication events, we can still assume S im = S mi . However, Rm i can not be considered as a constant and thus C in (5.2.10) changes in each time step. Thus we introduce the controller as below, T P˙ i = Rt − P Ti + P Tm − Rm i , (5.2.13) which converge to the desired value in a single time step. The discrete time representation of above is as follows, P Ti (k + 1) = Rt + P Tm − Rm (5.2.14) i (k), which only depends on the local RSSI measurements at the client nodes. 5.2.5 Experimental Results In the experimental evaluation we use two controller conﬁgurations, (i) Centralized implementation (see Figure 5.9(a)) and (ii) Decentralized implementation (see Figure 5.9(b)). For the centralized implementation the server node transmits the signal strength of the received signal back to the client node, which 84 Chapter 5. Communication and Power Saving Schemes ... Figure 5.10: Micaz node used for the experiment will be used in the power control process. This uses the controller conﬁguration expressed in the equation (5.2.7). In the distributed implementation, the client nodes make use of the local signal strength measurement for the power control process. For this approach the second conﬁguration of the power control algorithm expressed by the equation (5.2.10) is used. For the direct method of power control, the expression in (5.2.14) was used. The experimental evaluation is conducted with the Micaz transceivers developed by XBow technologies [193]. In Micaz hardware, the transmission power is controlled via an index (see [194] on mapping of the index to dBm). The experiments were done for two basic cases, (i) static environment where the gains of the communication does not change signiﬁcantly with in the time interval, and (ii) dynamic environment where the server node randomly moves within it’s communication range. We use ﬁve cases for each environment to study the performance of the control algorithms. The controller implementation in each client node is shown in the Table 5.3. Table 5.3: Client Nodes and Their Controllers Client No. 1 2 3 4 5 Control Algorithm/ function Centralized/ fL Centralized/ fS De-centralized/ fL De-centralized/ fS Direct Control Static Environment For this experiment we choose an environment with no or limited link gain variation (mostly due to the receiver noise). The Figures 5.11 and 5.12 shows the variation of received power measurements and the transmission power values of the client nodes. For this experiment, the target received power at the server node (Rt ) is selected as −70dBm. According to the experiment results, the centralized controllers perform an accurate power control than the decentralized ones. Moreover, the centralized controllers demonstrate more robustness to measurement errors comparing with the decentralized one. Chapter 5. Communication and Power Saving Schemes ... 10 10 Received Power at Client Received power at server Transmission power of client −10 −20 −30 −40 −50 −60 Received Power at Client Received power at server Transmission power of client 0 Power Level / (dBm) Power Level / (dBm) 0 −10 −20 −30 −40 −50 −60 −70 −80 0 85 −70 50 100 150 200 250 −80 0 300 50 100 150 Time Index (a) Centralized implementation of the linear controller 300 10 Received Power at Client Received power at server Transmission power of client −10 −20 −30 −40 −50 −60 Received Power at Client Received power at server Transmission power of client 0 Power Level / (dBm) 0 Power Level / (dBm) 250 (b) Centralized implementation of the sigmoid controller 10 −10 −20 −30 −40 −50 −60 −70 −80 0 200 Time Index −70 50 100 150 200 250 −80 0 300 50 100 150 Time Index 200 250 300 Time Index (c) De-centralized implementation of the linear controller (d) De-centralized implementation of the sigmoid controller Figure 5.11: Behavior of the iterative controller in a static environment 10 Received Power at Client Received power at server Transmission power of client Power Level / (dBm) 0 −10 −20 −30 −40 −50 −60 −70 −80 0 50 100 150 200 250 300 Time Index Figure 5.12: Implementation of the “Direct” controller. (Static Environment) Dynamic Environment The Figures 5.13 and 5.14 shows the variation of received power measurements and the transmission power values of the client nodes. The target received power at the server node (Rt ) is selected as −70dBm. In a dynamic environment, neither the centralized controllers nor the decentralized controllers perform well in maintaining a constant RSS at the server node. However, the centralized and decentralized implementation of the sigmoid function based controller performed well than the other controller conﬁgurations. Chapter 5. Communication and Power Saving Schemes ... 10 10 0 0 Power Level / (dBm) Power Level / (dBm) 86 −10 −20 −30 −40 Received Power at Client Received power at server Transmission power of client −50 −60 −70 −80 0 −10 −20 −30 Received Power at Client Received power at server Transmission power of client −40 −50 −60 −70 50 100 −80 0 150 50 Time Index (a) Centralized implementation of the linear controller 10 0 Power Level / (dBm) Power Level / (dBm) 0 −10 −20 −40 Received Power at Client Received power at server Transmission power of client −50 −60 −70 −80 0 150 (b) Centralized implementation of the sigmoid controller 10 −30 100 Time Index −10 −20 −30 Received Power at Client Received power at server Transmission power of client −40 −50 −60 −70 50 100 150 −80 0 50 Time Index 100 150 Time Index (c) De-centralized implementation of the linear controller (d) De-centralized implementation of the sigmoid controller Figure 5.13: Implementation of the iterative controller in a dynamic environment 10 Power Level / (dBm) 0 −10 −20 −30 −40 Received Power at Client Received power at server Transmission power of client −50 −60 −70 −80 0 50 100 150 Time Index Figure 5.14: Implementation of the “Direct” controller. (Dynamic Environment) 5.3 Discussion of implementation considerations 5.4 Summary The ﬁrst section of this chapter introduces an architecture for an all-to-all ad-hoc wireless network that satisﬁes the QoS requirements as well as power saving aspects. The CDMA based communication in the proposed network enables the operation in a very narrow band as well as maintaining a larger member base. Chapter 5. Communication and Power Saving Schemes ... 87 This makes this network extremely suitable for military, swarm robotics and sensor network applications that require larger member base dispersed in relatively close proximity (i.e. within the single hop range of the transmitters) and simultaneous / delay-free communication within the network. The simulation case studies illustrate the behavior of the controller in ideal conditions. Moreover, the theoretical assertions of network capacity and selection of target RSS value were illustrated. Moreover, the controller behavior in dynamic and real-world scenarios are tested using computer simulations. In the second section of the chapter we introduced a power control algorithm which uses RSSI measurements which is facilitated by most commercially available transceivers (in comparison with the CIR measurements presented in [173, 172] etc,). The wireless network considered in this section is directly applicable to typical data collection applications in a swarm robotic based distributed sensor network. Since the control scheme focuses on maintaining the least power required for the base station / mobile data collector to capture the data packet, the clients transmit the signal in the minimum possible power which ensure the optimal CIR for every client. This eﬀectively enhances the battery life of the power critical client nodes while maintaining a better quality of service. The experimental results verify the convergence of the power control scheme in a static environment as well as the practical applicability of the proposed controller. Chapter 6 Concluding Remarks This thesis has led to number of potential research directions in swarm robotics and wireless sensor networks arena. In this chapter we summarize the diﬀerent research aspects explored in the thesis and present them in an application case study. It provides the links between the seemingly standalone research outcomes as well as give an application value to the research. Many data gathering applications, such as monitoring entire catchment area of a lake, water quality monitoring of a reservoir, pollution monitoring in a selected ocean area (for example the great barrier reef in Australia), require a large wireless sensor network distributed evenly in the desired geographical area. In many situations this cannot be done manually, hence an self deployable wireless sensor deployment and a data gathering system would have an added application value to the environmental monitoring scientists. In this chapter we propose an airborne sensor network deployment and data gathering system which is entirely based on the multi-agent control strategies and wireless communication algorithms developed in this research. The Wireless Sensor Network Before describing the airborne deployment system, we ﬁrst discuss the applicability of a wireless sensor network with single-hop mobile data collector based environmental monitoring system. In a large environmental monitoring sensor network, which needs centralized processing of the sensor readings, the typical practice is to store the sensor reading over a time period in the wireless nodes and later send for centralized processing. 5 2 4 G 1 3 Figure 6.1: Uneven power consumption in a large multi-hop networks. This ﬁgure shows few multihopping branches in a multi-hop routing network, the dotted lines represents the multi-hop paths toward the Gate way( which is the ﬁnal destination of all the data - represented in red “G”). When the multihop network is enormously large, the neighboring nodes to the Gateway (nodes 1, 2 and 3) have more data transmission load than the rest of the network. In a randomly deployed wireless sensor network, comprising of homogeneous nodes, this could cause premature end to the network life. 89 90 Chapter 6. Concluding Remarks (a) Scattered Networks in self conﬁguring multi-hop scenario (b) Airborne mobile data collector can access every node along the path Figure 6.2: Geographical locations of the air deployed nodes creates few scattered networks instead of a large ad-hoc connected network. The cross-section of the geographical area in this ﬁgure represents a possible scenario of wireless node deployment. Note that this ﬁgure shows only the 2D distribution of the nodes along the cross section, however it represents the 3D distribution of the nodes and their connectivity. The sub ﬁgure (a) shows the appearance of scattered networks in the region which would not generate a functional multi-hop network. Sub ﬁgure (b) represents a scenario with a mobile data collector (air borne). It can access every node along the path of motion, which contributes to an eﬀective data collection from the sensor network. The mobile data collector based wireless sensor network employed in this case study have distinct advantages over the “popular” multi-hop routing based data collecting approach, specially in an application like environmental monitoring which consists of large number of energy critical nodes. For example, a node-to-node routing based data collecting scenario entails the generation of a massive routing tree which become impossible to store and process in a low power micro-controller based wireless nodes. Moreover, in many situation few middle nodes (aggregator nodes) may be used by many routing paths (see Figure 6.1) which creates uneven energy consumption in the network, causing premature end to the network life. Apart from that, the geographical distribution of the nodes in the airborne deployment system restricts the use of multi-hop routing (see Figure 6.2). In the wireless communication protocol we introduced in Chapter 5 - Section 2, the mobile data collector can simultaneously communicate with multiple sensory nodes within its range using a spreadspectrum protocol such as CDMA. This feature speeds up the data gathering process and provide the sensor nodes to send large data packets in a short period of time. Moreover the proposed wireless network controls the transmission power of each packet based on the “eﬀective distance” between the mobile data collector and the node. This ensures that every node in the network uses the minimum possible energy while maintaining the required received power for optimum Carrier to Interference Ratio at the mobile node for QoS guaranteed communication. The Airborne Deployment System In order to demonstrate every aspect of the research we select a wireless sensor network deployment scenario based on the swarming guided weapon system introduced in the chapter 4. Note that the controller for guided weapon system is derived from the basic controller (see chapter 3) introduced for a generic swarm robot control scenario. Moreover, this basic controller can be further modiﬁed for diﬀerent application scenarios. For example, the pattern generation terms (Fi,r and Fi,a ) of the basic controller can be modiﬁed by including a velocity term for tracking and generating a moving patterns which have high application value in automated formation ﬂights and space craft formations. Comparing with other pattern generation algorithms [64, 71, 65], the proposed scheme does not allocate the members with speciﬁc locations (which is extremely time consuming and some times impossible in a large environmental monitoring network) or have special members (such as virtual leaders) to control Chapter 6. Concluding Remarks 91 sections of the swarm. This eliminates any scalability and robustness issues which are inherent to such centralized systems. On the other hand, in our algorithm, the members are driven by a decentralized controller (every member uses the same controller and same weighing parameters) which navigate the entire airborne sensor system as a group eliminating the necessities for special members or to derive member speciﬁc weighing parameters. An airborne wireless sensor node is basically a ﬂying platform similar to a guided weapon (glided); containing the navigation controller, self localization capabilities (such as GPS and inertial), sensor devices and wireless communication equipments. Unlike the guided weapon navigation mechanisms, which needs to navigate a massive weapon with pin point accuracy, the navigation system in a airborne wireless sensor network deployment needs fairly simple control mechanisms in order to guide the light weight target. However, we do not discuss the hardware development of such airborne sensor in this dissertation and propose it as further work that could be done in parallel with this research. In relation with the wireless sensor network deployment, the airborne sensors need to be informed with the desired geographical area (as a sequence of points representing the contour of the region - see ﬁgure 4.13) and the weighing parameters for pattern generation (according to the selection criteria proposed in the chapter 4). Moreover, we provided a lower bound for the release height (hrel ) of the swarm, which guarantee that every sensor node drops inside the desired area when released higher than hrel . The control scheme however does not include any compensation for natural eﬀects such as wind and up-drifts which may cause the airborne system to navigate in an unpredictable manner, and they are identiﬁed as further improvements in this scheme. Internal Communications Another important component in navigating the airborne sensor system is the internal communication scheme which is used to share location information of the entire swarm. Instantaneous knowledge of the positions of the other members is utmost important for an airborne unit in avoiding collision among members as well as distributing the sensor network evenly within the desired geographical area. The all-to-all communication algorithm proposed in the chapter 5 (section 1) can be identiﬁed as the best candidate for such information sharing scheme. Since the proposed communication scheme enables a swarm member to send its location (and status) information to the entire swarm while receiving the same information from the others at the same time, it satisﬁes the condition “instantaneous knowledge of the location of the entire swarm”, which is a major assumption in the pattern generation theory. Moreover, the scheme provides with single-hop broadcasting methodology, which eliminate the routing tree generation in an mobile ad-hoc network as well as the delays occurred in a routing based data sharing algorithms. Furthermore, the communication scheme is optimized for battery life as well as the QoS of the communication links. Final Remark The above describes a potential application scenario which uses the aspects of the entire research / thesis. However, there are many other instances which can employ the ﬁndings of this research either partially or completely. Although this dissertation provides a solid foundation to a pattern generation (populate members inside a shape contour) solution, there exists many potential future work which will inevitably add extra application value. Among them, real-world implementation of the swarm robot control algorithm can be identiﬁed as a major portion. This could be done for either ground or airborne system, which include speciﬁc hardware platform development and controller modiﬁcation for kinematics of the target platform. Appendix I: Mathematical Function for Contour Generation For the simulation of the algorithm, the contour γ s are generated by a mathematical function in the following form, (a − b)θ (γ(θ)) = d (a − b)cos(θ) + c cos b (a − b)θ . (γ(θ)) = d (a − b)sin(θ) − c sin b (6.0.1) (6.0.2) The parameter a ∈ determines the number of edges in the contour. Parameter b = 1 for a simple closed contour and c determines the smoothness of the edges (c > 1 makes the edges to wind, c = 1 makes sharp edges and c < 1 results in round edges with c = 0 making a circle). Parameter d > 0 determines the overall size of the shape. Table 6.1: Properties of the function Parameter a Shape No of symmetrical axes 3 Triangular 3 4 Rectangular 4 . . . 8 Octagonal 8 . . . 92 Bibliography [1] E. Sahin, “Swarm robotics: From sources of inspiration to domains of application,” in Swarm Robotics, ser. Lecture Notes in Computer Science, 2005, pp. 10–20. [2] L. Bayindir and E. Sahin, “A review of studies in swarm robotics,” Turk J Elec Engin, vol. 15, no. 2, pp. 115–147, 2007. [3] V. Gazi and B. Fidan, “Coordination and control of multi-agent dynamic systems: Models and approaches,” in Swarm Robotics, ser. Lecture Notes in Computer Science, 2007, pp. 71–102. [4] S. W. Ekanayake and P. N. Pathirana, “Artiﬁcial formation forces for stable aggregation of multiagent system,” in Information and Automation, 2006. ICIA 2006. International Conference on, 2006, pp. 129–134. [5] ——, “Smart cluster bombs - control of multi-agent systems for military applications,” in Networking, Sensing and Control, 2007 IEEE International Conference on, 2007, pp. 471–476. [6] ——, “Geometric formations in swarm aggregation: An artiﬁcial formation force based approach,” in Information and Automation for Sustainability, 2007. ICIAfS 2007. International Conference on. [7] ——, “Two stage architecture for navigating multiple guided weapons into a widespread target,” in IEEE Aerospace conference 2008, BigSky, Montana, USA. [8] S. W. Ekanayake, P. N. Pathirana, and M. Palanaswami, “Maintaining optimal co-channel interference for power eﬃcient wireless communication,” in ISSNIP conference 2007, Melbourne, Australia. [9] S. W. Ekanayake, P. N. Pathirana, B. F. Rolfe, and M. Palanaswami, “Energy eﬃcient, fullyconnected mesh networks for high speed applications,” in IEEE Vehicular Technology Conference, VTC2008, Singapore. 93 94 Bibliography [10] U. http://www.shef.ac.uk/marcoms/eview/articles58/robot.htm, “A 13th century programmable robot,” The University of Sheﬃeld, 2007. [11] M. E. Rosheim, Leonardos Lost Robots, 1st ed. Springer Berlin Heidelberg, 2006. [12] U. http://www.robotics.utexas.edu/rrg/learn more/history, “Robotics Research Group- Learn More History,” The University of Texas at Austin, 2007. [13] R. Whiting, The Art of Leonardo Da Vinci - A portrait of the Renaissance man. London: Quantum Publishing Ltd, 2005. [14] M. Rosheim, “In the footsteps of leonardo [articulated anthropomorphic robot],” Robotics & Automation Magazine, IEEE, vol. 4, no. 2, pp. 12–14, Jun 1997. [15] E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm intelligence: from natural to artiﬁcial systems. US: Oxford University Press, 1999. [16] J. Kennedy, Swarm Intelligence, ser. Handbook of Nature-Inspired and Innovative Computing, 2006. [17] E. Bonabeau and C. Meyer, “Swarm intelligence: A whole new way to think about business,” Harward Business Review, pp. 106–114, May 2001. [18] M. Dorigo and G. D. Caro, “The ant colony optimization meta-heuristic,” New ideas in optimization, pp. 11–32, 1999. [19] M. Dorigo and T. Sttzle, Ant Colony Optimization. MIT Press, 2004. [20] A. Ratnaweera, S. Halgamuge, and H. Watson, “Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coeﬃcients,” Evolutionary Computation, IEEE Transactions on, vol. 8, no. 3, pp. 240–255, June 2004. [21] M. Clerc, Particle Swarm Optimization. ISTE Publishing Company, 2006. [22] F. Mondada, L. Gambardella, D. Floreano, S. Nolﬁ, J. Deneuborg, and M. Dorigo, “The cooperation of swarm-bots: physical interactions in collective robotics,” Robotics & Automation Magazine, IEEE, vol. 12, pp. 21–28, 2005. [23] G. Beni, “From swarm intelligence to swarm robotics,” in Swarm Robotics, 2005, pp. 1–9. [24] M. Krieger, J. Billeter, and L. Keller, “Ant-like task allocation and recruitment in cooperative robots,” Nature, vol. 406, pp. 992–995, August 2000. Bibliography 95 [25] D. M. Gordon, “The organization of work in social insect colonies,” Complexity, vol. 8(1), pp. 43–46, 2003. [26] I. Hamilton and L. Dill, “Group foraging by a kleptoparalastic ﬁsh: A strong inference test of social foraging models,” Ecology, vol. 84(12), pp. 3349–3359, 2003. [27] E. Robinson, D. Jackson, M. Holcomber, and F. Ratnieks, “’no entry’ signal in ant foraging,” Nature, vol. 438, p. 442, November 2005. [28] C. Brown and K. Warburton, “Social mechanisms enhance escape responses in schoals of rainbowﬁsh,” Environmental Biology of Fishes, vol. 56, pp. 455–459, 1999. [29] Y. Inada, “Steering mechanisms in ﬁsh schools,” Complexity International, vol. 8, pp. 43–46, 2001. [30] S. V. Grnbaum, D. and J. K. Parrish, “Extracting interactive control algorithms from group dynamics of schooling ﬁsh,” in Cooperative Control, ser. Lecture Notes in Control and Information Sciences. Berlin / Heidelberg: Springer, 2004, vol. 309, pp. 103–117. [31] C. Parker and H. Zhang, “Collective robotic site preparation,” Adaptive Behavior, vol. 14, no. 1, pp. 5–19, 2006. [32] C. W. Reynolds, “Flocks, Herds, and Schools: A Distributed Behavioral Model,” Computer Graphics, vol. 21, no. 4, pp. 25–34, 1987. [33] R. Burton, Bird Behavior. Alfred A. Knopf, Inc, 1985. [34] B. Partridge, “Structure and function of ﬁsh schools,” Scientiﬁc American, pp. 114–123, June 1982. [35] C. Breder, “Equations descriptive of ﬁsh schools and other animal aggregations,” Ecology, vol. 35, no. 3, pp. 361–370, 1954. [36] A. Okubo, “Dynamical Aspects of animal grouping: swarms, schools, ﬂocks, and herds,” Advances in Biophysics, vol. 22, pp. 1–94, 1986. [37] K. Warburton and J. Lazarus, “Tendency-distance models of social cohesion in animal groups,” Journal of Theoretical Biology, vol. 150, pp. 473–488, 1991. [38] D. Grunbaum and A. Okubo, “Modelling social animal aggregations,” in Frontiers in Theoretical Biology, ser. Lecture notes in Biomathematics. Springer-Verlag, New York, 1994, pp. 296–325. 96 Bibliography [39] V. Gazi and K. Passino, “A class of attraction/repulsion functions for stable swarm aggregations,” Decision and Control, 2002, Proceedings of the 41st IEEE Conference on, vol. 3, pp. 2842–2847, 2002. [40] ——, “Stability analysis of swarms,” Automatic Control, IEEE Transactions on, vol. 48, pp. 692– 697, 2003. [41] V. Gazi, “Swarm aggregations using artiﬁcial potentials and sliding-mode control,” Robotics, IEEE Transactions on [see also Robotics and Automation, IEEE Transactions on], vol. 21, Issue 6, pp. 1208–1214, 2005. [42] V. Gazi and K. Passino, “Stability analysis of social foraging swarms,” Systems, Man and Cybernetics, Part B, IEEE Transactions on, vol. 34, pp. 539–557, 2004. [43] L. Yang, K. Passino, and M. Polycarpou, “Stability analysis of m-dimensional asynchronous swarms with a ﬁxed communication topology,” Automatic Control, IEEE Transactions on, vol. 48, pp. 76– 95, 2003. [44] Y. Liu and K. Passino, “Stable social foraging swarms in a noisy environment,” Automatic Control, IEEE Transactions on, vol. 49, Issue 1, pp. 30–44, 2004. [45] L. Yang, K. Passino, and M. Polycarpou, “Stability analysis of one-dimensional asynchronous swarms,” Automatic Control, IEEE Transactions on, vol. 48, pp. 1848–1854, 2003. [46] O. Soysal and E. Sahin, “Probabilistic aggregation strategies in swarm robotic systems,” Swarm Intelligence Symposium, Proceedings 2005 IEEE, pp. 325–332, June 2005. [47] V. Trianni, T. Labella, R. Grob, E. Sahin, M. Dorigo, and J. Deneubourg, “Modeling Pattern Formation in a Swarm of Self-Assembling Robots,” Technical Report TR/IRIDIA/2002-12, IRIDIA, Universit Libre de Bruxelles, Bruxelles, Belgium, May 2002. [48] K. Naruse, H. Yokoi, M. Kinoshita, and Y. Kakazu, “Group formation of agents with twodimensional inner state and one-to-one subjective evaluation,” Proceedings IEEE International Symposium on Computational Intelligence in Robotics and Automation ,, vol. 3, pp. 1492– 1497, 2003. [49] E. Bahceci and E. Sahin, “Evolving aggregation behaviors for swarm robotic systems: A systematic case study,” Swarm Intelligence Symposium, Proceedings 2005 IEEE. Bibliography 97 [50] V. Trianni, R. Grob, T. Labella, E. Sahin, and M. Dorigo, “Evolving Aggregation Behaviors in a Swarm of Robots,” in Advances in Artiﬁcial Life - Proceedings of the 7th Europian Conference on Artiﬁcial Life (ECAL), ser. Lecture notes in Artiﬁcial Intelligence. Springer Verlag, Heidelberg, Germany, 2003, pp. 865–874. [51] T. Vicsek, A. Czir´ok, E. Ben-Jacob, I. Cohen, and O. Shochet, “Novel type of phase transition in a system of self-driven particles,” Phys. Rev. Lett., vol. 75, no. 6, pp. 1226–1229, Aug 1995. [52] A. Jadbabaie, J. Lin, and A. Morse, “Coordination of groups of mobile autonomous agents using nearest neighbor rules,” Automatic Control, IEEE Transactions on, vol. 48, no. 6, pp. 988–1001, June 2003. [53] R. Olfati-Saber, “Flocking for multi-agent dynamic systems: Algorithms and theory,” IEEE Transactions on Automatic Control, vol. 51, pp. 401–420, March 2006. [54] A. Tanner, Herbert G.and Jadbabaie and G. J. Pappas, “Flocking in Teams of Nonholonomic Agents,” in in S. Morse, N. Leonard and V. Kumar (eds.), Cooperative Control, ser. Lecture Notes in Control and Information Sciences. Springer-Verlag, 2005, pp. 229–239. [55] H. Tanner, A. Jadbabaie, and G. Pappas, “Stable ﬂocking of mobile agents part i: dynamic topology,” Decision and Control, 2003. Proceedings. 42nd IEEE Conference on, vol. 2, pp. 2016–2021, 9-12 Dec. 2003. [56] ——, “Stable ﬂocking of mobile agents, part i: ﬁxed topology,” Decision and Control, 2003. Proceedings. 42nd IEEE Conference on, vol. 2, pp. 2010–2015, 9-12 Dec. 2003. [57] H. Ando, Y. Oasa, I. Suzuki, and M. Yamashita, “Distributed memoryless point convergence algorithm for mobile robots with limited visibility,” Robotics and Automation, IEEE Transactions on, vol. 15, no. 5, pp. 818–828, Oct 1999. [58] J. Lin, A. Morse, and B. Anderson, “The multi-agent rendezvous problem,” Decision and Control, 2003. Proceedings. 42nd IEEE Conference on, vol. 2, pp. 1508–1513, 9-12 Dec. 2003. [59] ——, “The multi-agent rendezvous problem - the asynchronous case,” Decision and Control, 2004. CDC. 43rd IEEE Conference on, vol. 2, pp. 1926–1931, 14-17 Dec. 2004. [60] G. Conte and P. Pennesi, “On convergence conditions for rendezvous,” Decision and Control, 2007 46th IEEE Conference on, pp. 2375–2378, 12-14 Dec. 2007. 98 Bibliography [61] A. Tiwari, J. Fung, I. Carson, J.M., R. Bhattacharya, and R. Murray, “A framework for lyapunov certiﬁcates for multi-vehicle rendezvous problems,” American Control Conference, 2004. Proceedings of the 2004, vol. 6, pp. 5582–5587, 30 June-2 July 2004. [62] Y. Q. Chen and Z. Wang, “Formation control: a review and a new consideration,” Intelligent Robots and Systems, 2005. (IROS 2005). 2005 IEEE/RSJ International Conference on, pp. 3181– 3186, 2005. [63] G. Antonelli and S. Chiaverini, “Kinematic control of platoons of autonomous vehicles,” Robotics, IEEE Transactions on, December 2006. [64] J. Desai, J. Ostrowski, and V. Kumar, “Controlling formations of multiple mobile robots,” Proc. IEEE Int. Conf. Robotics Automation, Leuven, Belgium, pp. 2864–2869, 1998. [65] H. Tanner, G. Pappas, and V. Kumar, “Leader-to-formation stability,” Robotics and Automation, IEEE Transactions on, vol. 29, pp. 443–455, 2004. [66] V. Gazi, “Formation control of a multi-agent system using decentralized nonlinear servomechanism,” Decision and Control, 2003. Proceedings. 42nd IEEE Conference on, vol. 3, pp. 2531–2536, 2003. [67] N. Leonard and E. Fiorelli, “Virtual leaders, artiﬁcial potentials and coordinated control of groups,” Decision and Control, 2001. Proceedings of the 40th IEEE Conference on, vol. 3, pp. 2968–2973, 2001. [68] M. Egerstedt and X. Hu, “Formation constrained multi-agent control,” Robotics and Automation, IEEE Transactions on, vol. 17, pp. 947–951, 2001. [69] X. Xi and E. Abed, “Formation control with virtual leaders and reduced communications,” Decision and Control, 2005. Proceedings of the 44th IEEE Conference on, pp. 1854–1860, 2005. [70] H. Hsu and A. Liu, “Applying a taxonomy of formation control in developing a robotic system,” Tools with Artiﬁcial Intelligence, 2005. ICTAI 05. 17th IEEE International Conference on, pp. 3–10, 2005. [71] J. Spletzer and R. Fierro, “Optimal positioning strategies for shape changes in robot teams,” Robotics and Automation, 2005. ICRA 2005. Proceedings of the 2005 IEEE International Conference on, pp. 742–747, 2005. Bibliography 99 [72] T. Balch and R. Arkin, “Behavior-based formation control for multirobot teams,” Robotics and Automation, IEEE Transactions on, vol. 14, pp. 926–939, 1998. [73] K. Sugihara and I. Suzuki, “Distributed algorithms for formation of geometric patterns with many mobile robots,” Journal of Robotic Systems, vol. 13, no. 3, pp. 127–139, 1996. [74] I. Suzuki and M. Yamashita, “Distributed autonomous mobile robots: Formation of geometric patterns,” SIAM J Comput, vol. 29, no 4, pp. 1347–1363, 1999. [75] W. Spears, D. Spears, J. Hamann, and R. Heil, “Distributed, physics-based control of swarms of vehicles,” Autonomous Robots, vol. 17, no. 2, pp. 137–162, 2004. [76] S. Nouyan and M. Dorigo, “Chain formation in a swarm of robots,” IRIDIA, Universit´e Libre de Bruxelles, Tech. Rep. TR/IRIDIA/2004-18, March 2004. [77] R. Grob, M. Bonani, F. Mondada, and M. Dorigo, “Autonomous self-assembly in a swarmbot,” Proceedings of the third international symposium on autonomous minirobots for research edutainment, pp. 314–322, 2006. [78] D. Payton, M. Dally, R. Estkowski, M. Howard, and C. Lee, “Pheromone robotics,” Autonomous Robots, vol. 11, no. 3, pp. 314–322, 2001. [79] D. Payton, R. Estkowski, and M. Howard, “Pheromone robotics and the logic of virtual pheromones,” SAB 2004, pp. 45–57, 2004. [80] W. Shen, C. Chuong, and P.Will, “Simulating self-organization for multi-robot systems,” International Conference on Intelligent and Robotic Systems, 2002. [81] W. Shen, P. Will, A. Galstyan, and C. Chuong, “Hormone-inspired self-organization and distributed control of robotic swarms,” Autonomous Robots, vol. 17, pp. 93–105, 2004. [82] J. Reif and H. Wang, “Social potential ﬁelds: A distributed behavioral control for autonomous robots,” Robot. Auton. Syst., vol. 8, no. 5, pp. 171–194, 1999. [83] D. Kim, H. Wang, G. Ye, and S. Shin, “Decentralized control of autonomous swarm systems using artiﬁcial potential functions: Analytical design guidelines,” 43rd IEEE Conference on Decision and Control, Atlantis, Paradise Island, Bahamas, pp. 159–164, 2004. 100 Bibliography [84] T. Tsuji, Y. Tanaka, P. Morasso, V. Sanguineti, and M. Kaneko, “Bio-mimetic trajectory generation of robots via artiﬁcial potential ﬁeld with time base generator,” IEEE Transactions on Systems, Man, and Cybernetic-Part C: Applications and Reviews, vol. 32, no. 4, pp. 426–439, 2002. [85] L. Chaimowicz, N. Michael, and V. Kumar, “Controlling swarms of robots using interpolated implicit functions,” Proc. IEEE Int. Conf. Robotics Automation, Barcelona, Spain, pp. 2487–2492, 2005. [86] V. Gazi and K. Passino, “A class of attraction/repulsion functions for stable swarm aggregations,” Decision and Control, 2002, Proceedings of the 41st IEEE Conference on, vol. 3, pp. 2842–2847, 10-13 Dec. 2002. [87] R. Bachmayer and N. Leonard, “Vehicle networks for gradient decent in a sampled environment,” Decision and Control, 2002. Proceedings of the 40th IEEE Conference on, pp. 112–117, 2002. [88] W. Spears and D. Gordon, “Using artiﬁcial physics to control agents,” Information Intelligence and Systems, 1999. Proceedings. 1999 International Conference on, pp. 281–288, 1999. [89] W. M. Spears, D. F. Spears, R. Heil, W. Kerr, and S. Hettiarachchi, “An overview of physicomimetics,” Lecture Notes in Computer Science, Swarm Robotics, pp. 84–97, 2005/// 2005. [90] W. Spears, D. Spears, and R. Heil, “A formal analysis of potential energy in a multi-agent system,” Lecture Notes in Computer Science, Formal Approaches to Agent-Based Systems, pp. 131–145, 2005. [91] D. Spears, D. Zarzhitsky, and D. Thayer, “Multi-robot chemical plume tracing,” Multi-Robot Systems. From Swarms to Intelligent Automata, vol. III, pp. 211–221, 2005. [92] D. Zarzhitsky, D. Spears, D. Thayer, and W. Spears, “Agent-based chemical plume tracing using ﬂuid dynamics,” Lecture Notes in Computer Science, Formal Approaches to Agent-Based Systems, pp. 146–160, 2005. [93] D. Zarzhitsky, D. Spears, W. Spears, and D. Thayer, “A ﬂuid dyanmics approach to multi-robot chemical plume tracing,” Autonomous Agents and Multiagent Systems, 2004. AAMAS 2004. Proceedings of the Third International Joint Conference on, pp. 1476–1477, 2004. [94] T. Balch, F. Dellaert, A. Feldman, A. Guillory, J. Isbell, C.L., Z. Khan, S. Pratt, A. Stein, and H. Wilde, “How multirobot systems research will accelerate our understanding of social animal behavior,” Proceedings of the IEEE, vol. 94, no. 7, pp. 1445–1463, 2006. Bibliography 101 [95] C. Harper and A. Winﬁeld, “A methodology for provably stable intelligent control,” Robotics and Autonomous Systems, vol. 54, no. 1, pp. 52–73, 2006. [96] S. Gueron and S. Levin, “The dynamics of group formation,” Mathematical Biosciences, vol. 128, pp. 243–264, 1995. [97] O. Soysal and E. Sahin, “A macroscopic model for probabilistic aggregation in swarm robotic systems,” In Sahin et al., E., ed.: Proc of SAB06 Workshop on Swarm Robotics. Lecture Notes in Computer Science (LNCS), Springer Verlag, 2006. [98] W. Agassounon, A. Martinoli, and K. Easton, “Macroscopic modeling of aggregation experiments using embodied agents in teams of constant and time-varying sizes,” Autonomous Robots, vol. 17, no. 2-3. [99] R. Goebel, C. Prieur, and A. Teel, “Smooth patchy control lyapunov functions,” Decision and Control, 2006 45th IEEE Conference on, pp. 3271–3276, 2006. [100] P. Ogren, M. Egerstedt, and X. Hu, “A control lyapunov function approach to multi-agent coordination,” Decision and Control, 2001. Proceedings of the 40th IEEE Conference on, vol. 2, pp. 1150–1155, 2001. [101] ——, “A control lyapunov function approach to multiagent coordination,” Robotics and Automation, IEEE Transactions on, vol. 18, no. 5, pp. 847–851, 2002. [102] J. Desai, J. Ostrowski, and V. Kumar, “Modeling and control of formations of nonholonomic mobile robots,” Robotics and Automation, IEEE Transactions on, vol. 17, no. 6, pp. 905–908, Dec 2001. [103] W. Dong and Y. Guo, “Formation control of nonholonomic mobile robots using graph theoretical methods,” Applied Optimization, Cooperative Control and Optimization, pp. 369–386, 2007. [104] R. Fierro, P. Song, A. Das, and V. Kumar, “Cooperative control of robot formations,” Lecture Notes in Economics and Mathematical System, Cooperative Systems, pp. 73–93, 2002. [105] J. Desai, “Modeling multiple teams of mobile robots: a graph theoretic approach,” Intelligent Robots and Systems, 2001. Proceedings. 2001 IEEE/RSJ International Conference on, vol. 1, pp. 381–386, 2001. [106] J. La Salle and S. Lefschetz, Stability by Liapunov’s Direct Method With Applications, ser. Mathematics in Science and Engineering. Academic Press Inc (London) Ltd., 1967, vol. 4. 102 Bibliography [107] R. Horn and C. Johnson, Matrix Analysis. Cambridge: Cambridge University Press, 1985. [108] R. S. Varga, Matrix Iterative Analysis, ser. Prentis Hall Series in Automaic Computation. N.J.: Prentis Hall, Inc., 1962. [109] M.-Y. A. Hsieh and V. Kumar, “Pattern generation with multiple robots,” Proc. IEEE Int. Conf. Robotics Automation, Orlando, Florida, pp. 2442–2447, 2006. [110] D. Holeman, “Impact of 1-meter GPS navigation on war ﬁghting,” Position Location and Navigation Symposium, 1996., IEEE 1996, pp. 530–537, Apr 1996. [111] G. Graham and A. Killen, “GPS navigation requirements for future mobile ground-based missile systems,” in Position Location and Navigation Symposium, 1992. Record. ’500 Years After Columbus - Navigation Challenges of Tomorrow’. IEEE PLANS ’92., IEEE, 1992, pp. 419–421. [112] E. Gai, “The century of inertial navigation technology,” in Aerospace Conference Proceedings, 2000 IEEE, vol. 1, 2000, pp. 59–60 vol.1. [113] R. Bajaj, S. L. Ranaweera, and D. P. Agrawal, “GPS: Location-tracking technology,” Computer, pp. 92–94, April 2002. [114] “Aviation electronics/avionics,” Aerospace and Electronic Systems Magazine, IEEE, vol. 15, no. 10, pp. 47–61, 2000. [115] D. Pedlar and D. Coe, “Target geolocation using SAR,” Radar, Sonar and Navigation, IEE Proceedings -, vol. 152, no. 1, pp. 35–42, 2005. [116] J. Sherman, R. Davis, W. Owens, and J. Valdes, “The autonomous underwater glider ”spray”,” Oceanic Engineering, IEEE Journal of, vol. 26, no. 4, pp. 437–446, 2001. [117] J. Goodman, “Application of GPS navigation to space ﬂight,” in Aerospace, 2005 IEEE Conference, 2005, pp. 1837–1852. [118] X. Lin, T. Kirubarajan, Y. Bar-Shalom, and X. Li, “Enhanced accuracy GPS navigation using the interacting multiple model estimator,” in Aerospace Conference, 2001, IEEE Proceedings., vol. 4, 2001, pp. 4/1911–4/1923 vol.4. [119] D. Pittman and C. Roberts, “Determining GPS anti-jamming performance on tactical missiles,” in Position Location and Navigation Symposium, 1994., IEEE, 1994, pp. 641–648. Bibliography 103 [120] W. Caldwell, “Analysis of mission computer utilization of the GPS navigation solution during a simulated ﬁghter/attack scenario,” in Position Location and Navigation Symposium, 1988. Record. ’Navigation into the 21st Century’. IEEE PLANS ’88., IEEE, 1988, pp. 165–170. [121] T. Loﬄer and J. Nielson, “International harm precision navigation upgrade. a GPS/INS missile upgrade that improves eﬀectiveness and minimizes friendly-ﬁre accidents,” in Position Location and Navigation Symposium, 2002 IEEE, 2002, pp. 106–112. [122] G. Hyslop, D. Gerth, and J. Kraemer, “GPS/INS integration on the standoﬀ land attack missile (slam),” Aerospace and Electronic Systems Magazine, IEEE, vol. 5, no. 7, pp. 29–34, 1990. [123] ——, “GPS/INS integration on the standoﬀ land attack missile (slam),” in Position Location and Navigation Symposium, 1990. Record. ’The 1990’s - A Decade of Excellence in the Navigation Sciences’. IEEE PLANS ’90., IEEE, 1990, pp. 407–412. [124] P. Renfroe, J. McMinemon, and P. Couch, “Test and evaluation of the rockwell collins GNP-10 for the precision kill and targeting (PKAT) missile system,” in Position Location and Navigation Symposium, IEEE 2000, 2000, pp. 488–493. [125] A. Gamble and P. Jenkins, “Low cost guidance for the multiple launch rocket system (MLRS) artillery rocket,” in Position Location and Navigation Symposium, IEEE 2000, 2000, pp. 193–199. [126] B. Nguyen, Y.-L. Chuang, D. Tung, C. Hsieh, Z. Jin, L. Shi, D. Marthaler, A. Bertozzi, and R. Murray, “Virtual attractive-repulsive potentials for cooperative control of second order dynamic vehicles on the caltech mvwt,” American Control Conference, 2005. Proceedings of the 2005, vol. 2, pp. 1084–1089, 2005. [127] S. S. Ge, C.-H. Fua, and W.-M. Liew, “Swarm formations using the general formation potential function,” Robotics, Automation and Mechatronics, 2004 IEEE Conference on, vol. 2, pp. 655–600, 2004. [128] F. Ganji and S. Joshi, “Adaptive formation control for rovers travelling over unknown terrain,” Journal of Guidance, Control and Dynamics, vol. 29, no. 3, pp. 714–724, May-June 2006. [129] W. Ren and R. Beard, “Decentralized scheme for spacecraft formation ﬂying via the virtual structure approach,” Journal of Guidance, Control and Dynamics, vol. 27, no. 1, pp. 73–82, January-February 2004. 104 Bibliography [130] M. Patcher, J. D’Azzo, and A. Proud, “Tight formation ﬂight control,” Journal of Guidance, Control and Dynamics, vol. 24, no. 2, pp. 246–254, March-April 2001. [131] E. Yang, Y. Masuko, and T. Mita, “Dual controller approach to three-dimensional autonomous formation control,” Journal of Guidance, Control and Dynamics, vol. 27, no. 3, pp. 336–346, MayJune 2004. [132] R. Sattigeri and A. Calise, “An adaptive vision-based approach to decentralized formation control,” Journal of Aerospace Computing, Information and Communication, vol. 1, pp. 502–525, December 2004. [133] D. Stilwell, B. Bishop, and C. Sylvester, “Redundant manipulator techniques for partially decentralized path planning and control of a platoon of autonomous vehicles,” Systems, Man and Cybernetics, Part B, IEEE Transactions on, vol. 35, no. 4, pp. 842–848, 2005. [134] B. Bishop, “On the use of redundant manipulator techniques for control of platoons of cooperating robotic vehicles,” Systems, Man and Cybernetics, Part A, IEEE Transactions on, vol. 33, no. 5, pp. 608–615, 2003. [135] H. Yamaguchi and J. Burdick, “Asymptotic stabilization of multiple nonholonomic mobile robots forming group formations,” in Robotics and Automation, 1998. Proceedings. 1998 IEEE International Conference on, vol. 4, 1998, pp. 3573–3580. [136] F. Giulietti, L. Pollini, and M. Innocenti, “Autonomous formation ﬂight,” IEEE Control Systems Magazine, pp. 34–44, December 2000. [137] S. Kalantar and U. Zimmer, “Contour shaped formation control for autonomous underwater vehicles using canonical shape descriptors and deformable models,” OCEANS ’04. MTS/ IEEE TECHNOOCEAN ’04, pp. 296–307, 2004. [138] S. Ekanayake and P. Pathirana, “Smart cluster bombs - control of multi-agent systems for military applications,” Proc. IEEE Int. Conf. Network, Sensing and Control, London, UK, pp. 471–476, April 2007. [139] B. Lubachevsky and R. Graham, “Curved hexagonal packings of equal disks in a circle,” Discrete & Computational Geometry, vol. 18, pp. 197–194, 1997. Bibliography 105 [140] P. Szab, T. Csendes, L. Casado, and I. Garca, “Packing equal circles in a square i. - problem setting and bounds for optimal solutions,” Optimization Theory: Recent Developments from Mtrahza, vol. 18, pp. 191–206, 2001. [141] Y. Hwang and N. Ahuja, “A potential ﬁeld approach to path planning,” Robotics and Automation, IEEE Transactions on, vol. 8, no. 1, pp. 23–32, 1992. [142] O. Khatib, “Real-time obstacle avoidance for manipulators and mobile robots,” in Robotics and Automation. Proceedings. 1985 IEEE International Conference on, vol. 2, 1985, pp. 500–505. [143] ——, “Real-time obstacle avoidance for manipulators and mobile robots,” vol. 5, no. 1, pp. 90–98, 1986. [144] M. G. Park, J. H. Jeon, and M. C. Lee, “Obstacle avoidance for mobile robots using artiﬁcial potential ﬁeld approach with simulated annealing,” in Industrial Electronics, 2001. Proceedings. ISIE 2001. IEEE International Symposium on, vol. 3, 2001, pp. 1530–1535 vol.3. [145] J. Schiller, Mobile Communications, 2nd ed. Addison-Wesley, 2003. [146] R. Bruno, M. Conti, and E. Gregori, “Mesh networks: commodity multihop ad hoc networks,” Communications Magazine, IEEE, vol. 43, no. 3, pp. 123–131, 2005. [147] M. Lee, J. Zheng, Y.-B. Ko, and D. Shrestha, “Emerging standards for wireless mesh technology,” Wireless Communications, IEEE [see also IEEE Personal Communications], vol. 13, no. 2, pp. 56–63, 2006. [148] J. Jun and M. Sichitiu, “The nominal capacity of wireless mesh networks,” Wireless Communications, IEEE [see also IEEE Personal Communications], vol. 10, no. 5, pp. 8–14, 2003. [149] R. Hincapie, J. Sierra, and R. Bustamante, “Remote locations coverage analysis with wireless mesh networks based on ieee 802.16 standard,” Communications Magazine, IEEE, vol. 45, no. 1, pp. 120–127, 2007. [150] K. Almeroth, “The evolution of multicast: from the mbone to interdomain multicast to internet2 deployment,” Network, IEEE, vol. 14, no. 1, pp. 10–20, 2000. [151] Y. Chan, J. Modestino, Q. Qu, and X. Fan, “An end-to-end embedded approach for multicast/broadcast of scalable video over multiuser cdma wireless networks,” Multimedia, IEEE Transactions on, vol. 9, no. 3, pp. 655–667, 2007. 106 Bibliography [152] M.-S. Chen, J.-C. Chen, and P. Yu, “On general results for all-to-all broadcast,” Parallel and Distributed Systems, IEEE Transactions on, vol. 7, no. 4, pp. 363–370, 1996. [153] Y. Yang and J. Wang, “Pipelined all-to-all broadcast in all-port meshes and tori,” Transactions on Computers, vol. 50, no. 10, pp. 1020–1032, 2001. [154] W. Jia, L. Cheng, and G. Xu, “Eﬃcient multicast routing algorithms on mesh networks,” Algorithms and Architectures for Parallel Processing, 2002. Proceedings. Fifth International Conference on, pp. 110–117, 2002. [155] S.-C. Kim and K. Shin, “A performance analysis of manet multicast routing algorithms with multiple sources,” Software Engineering Research, Management & Applications, 2007. SERA 2007. 5th ACIS International Conference on, pp. 73–82, 20-22 Aug. 2007. [156] I. F. Akyildiz, E. Ekici, and G. Yue, “A distributed multicast routing scheme for multi-layered satellite ip networks,” Wireless Networks, vol. 9, no. 5, pp. 535–544, 2003. [157] S. Guo and O. Yang, “A constraint formulation for minimum-energy multicast routing in wireless multihop ad-hoc networks,” Wireless Networks, vol. 12, no. 1, pp. 23–32, 2006. [158] M. Transier, H. F¨ ubler, J. Widmer, M. Mauve, and W. Eﬀelsberg, “A hierarchical approach to position-based multicast for mobile ad-hoc networks,” Wireless Networks, vol. 13, no. 4, pp. 447– 460, 2007. [159] L.-L. Yang, “Mimo-assisted space-code-division multiple-access: linear detectors and performance over multipath fading channels,” Selected Areas in Communications, IEEE Journal on, vol. 24, no. 1, pp. 121–131, 2006. [160] Y. Yang and J. Wang, “On blocking probability of multicast networks,” Communications, IEEE Transactions on, vol. 46, no. 7, pp. 957–968, 1998. [161] ——, “Near-optimal all-to-all broadcast in multidimensional all-port meshes and tori,” Parallel and Distributed Systems, IEEE Transactions on, vol. 13, no. 2, pp. 128–141, 2002. [162] F. Ellersick, “A conversation with claude shannon,” Communications Magazine, IEEE, vol. 22, no. 5, pp. 123–126, 1984. [163] G. Cooper and R. Nettleton, “A spread-spectrum technique for high-capacity mobile communications,” Vehicular Technology, IEEE Transactions on, vol. 27, no. 4, pp. 264–275, 1978. Bibliography 107 [164] R. Prasad and T. Ojanpera, “A survey on cdma: evolution towards wideband cdma,” in Spread Spectrum Techniques and Applications, 1998. Proceedings., 1998 IEEE 5th International Symposium on, vol. 1, 1998, pp. 323–331 vol.1. [165] R. Scholtz, “The evolution of spread-spectrum multiple-access communications,” in Spread Spectrum Techniques and Applications, 1994. IEEE ISSSTA ’94., IEEE Third International Symposium on, 1994, pp. 4–13 vol.1. [166] D. Knisely, S. Kumar, S. Laha, and S. Nanda, “Evolution of wireless data services: Is-95 to cdma2000,” Communications Magazine, IEEE, vol. 36, no. 10, pp. 140–149, 1998. [167] K. Gilhousen, I. Jacobs, R. Padovani, A. Viterbi, J. Weaver, L.A., and I. Wheatley, C.E., “On the capacity of a cellular cdma system,” Vehicular Technology, IEEE Transactions on, vol. 40, no. 2, pp. 303–312, 1991. [168] J. Zander, “Performance of optimum transmitter power control in cellular radio systems,” Vehicular Technology, IEEE Transactions on, vol. 41, no. 1, pp. 57–62, 1992. [169] S. Grandhi, R. Vijayan, D. Goodman, and J. Zander, “Centralized power control in cellular radio systems,” Vehicular Technology, IEEE Transactions on, vol. 42, no. 4, pp. 466–468, 1993. [170] S. Grandhi, R. Vijayan, and D. Goodman, “Distributed power control in cellular radio systems,” Communications, IEEE Transactions on, vol. 42, no. 234, pp. 226–228, 1994. [171] S. Grandhi, R. Yates, and D. Goodman, “Resource allocation for cellular radio systems,” Vehicular Technology, IEEE Transactions on, vol. 46, no. 3, pp. 581–587, 1997. [172] G. Foschini and Z. Miljanic, “A simple distributed autonomous power control algorithm and its convergence,” vol. 42, pp. 249–257, 2004. [173] Z. Uykan and H. Koivo, “Sigmoid-basis nonlinear power-control algorithm for mobile radio systems,” Vehicular Technology, IEEE Transactions on, vol. 53, no. 1, pp. 265–270, 2004. [174] ——, “Proportional power control algorithm for time varying link gains in cellular radio systems,” Vehicular Technology, IEEE Transactions on, vol. 55, no. 1, pp. 341–349, 2006. [175] M. Cai, W. Wang, and H. S. Zhang, “Power control algorithm for time-varying cdma cellular systems,” Proceedings of 2004 International Conference on Intelligent Mechatronics and Automation, pp. 605–610, 2004. 108 Bibliography [176] D. Vengerov, N. Bambos, and H. Berenji, “A fuzzy reinforcement learning approach to power control in wireless transmitters,” Systems, Man and Cybernetics, Part B, IEEE Transactions on, vol. 35, no. 4, pp. 768–778, 2005. [177] Y. Hou, Y. Shi, J. Pan, and S. Midkiﬀ, “Maximizing the lifetime of wireless sensor networks through optimal single-session ﬂow routing,” Mobile Computing, IEEE Transactions on, vol. 5, no. 9, pp. 1255–1266, 2006. [178] T. Klein and H. Viswanathan, “Centralized power control and routing policies for multihop wireless networks,” Information Theory, IEEE Transactions on, vol. 52, no. 3, pp. 849–866, 2006. [179] T. ElBatt and A. Ephremides, “Joint scheduling and power control for wireless ad hoc networks,” Wireless Communications, IEEE Transactions on, vol. 3, no. 1, pp. 74–85, 2004. [180] Y. Zhou, M. Lyu, and J. Liu, “On setting up energy-eﬃcient paths with transmitter power control in wireless sensor networks,” in Mobile Adhoc and Sensor Systems Conference, 2005. IEEE International Conference on, 2005, p. 9 pp. [181] J. Gomez and A. Campbell, “Variable-range transmission power control in wireless ad hoc networks,” Mobile Computing, IEEE Transactions on, vol. 6, no. 1, pp. 87–99, 2007. [182] P. Nar and E. Cayirci, “PCSMAC: a power controlled sensor-MAC protocol for wireless sensor networks,” in Wireless Sensor Networks, 2005. Proceeedings of the Second European Workshop on, 2005, pp. 81–92. [183] S. Lin, J. Zhang, G. Zhou, L. Gu, J. A. Stankovic, and T. He, “ATPC: adaptive transmission power control for wireless sensor networks http://doi.acm.org/10.1145/1182807.1182830,” in Proceedings of the 4th international conference on Embedded networked sensor systems. Boulder, Colorado, USA: ACM Press, 2006, pp. 223–236. [184] S. Lim, K. Leong, and T. Itoh, “Adaptive power controllable retrodirective array system for wireless sensor server applications,” Microwave Theory and Techniques, IEEE Transactions on, vol. 53, no. 12, pp. 3735–3743, 2005. [185] V. Erceg, L. Greenstein, S. Tjandra, S. Parkoﬀ, A. Gupta, B. Kulic, A. Julius, and R. Bianchi, “An empirically based path loss model for wireless channels in suburban environments,” Selected Areas in Communications, IEEE Journal on, vol. 17, no. 7, pp. 1205–1211, 1999. Bibliography 109 [186] R. Santos, O. Alvarez, and A. Edwards, “Experimental analysis of wireless propagation models with mobile computing applications,” in Electrical and Electronics Engineering, 2005 2nd International Conference on, 2005, pp. 40–43. [187] W. Tam and V. Tran, “Propagation modelling for indoor wireless communication,” Electronics & Communication Engineering Journal, vol. 7, no. 5, pp. 221–228, 1995. [188] R. Sato, H. Sato, and H. Shirai, “A SBR estimation for indoor wave propagation through dielectric walls,” in Antennas and Propagation Society International Symposium, 2005 IEEE, vol. 2B, 2005, pp. 719–722 vol. 2B. [189] D. Puccinelli and M. Haenggi, “Multipath fading in wireless sensor networks: measurements and interpretation http://doi.acm.org/10.1145/1143549.1143757,” in Proceeding of the 2006 international conference on Communications and mobile computing. Vancouver, British Columbia, Canada: ACM Press, 2006, pp. 1039–1044. [190] V. Degli-Esposti, G. Lombardi, and C. Passerini, “Measurement and ray-tracing prediction of indoor channel parameters,” Electronics Letters, vol. 34, no. 22, pp. 2167–2168, 1998. [191] K. Remley, H. Anderson, and A. Weisshar, “Improving the accuracy of ray-tracing techniques for indoor propagation modeling,” Vehicular Technology, IEEE Transactions on, vol. 49, no. 6, pp. 2350–2358, 2000. [192] F. Agelet, F. Fontan, and A. Formella, “Fast ray tracing for microcellular and indoor environments,” Magnetics, IEEE Transactions on, vol. 33, no. 2, pp. 1484–1487. [193] Crossbow Technologies Incorporated, “http://www.xbow.com.” [194] “C2240 Transceiver Datasheet,” Chipcon Systems, 2004.

Formation Of Networked Mobile Robots

Rating

Date

Size

Views

Categories

Share

Transcript

Forgot your password?.