IROS2019国际学术会议论文集 1807

Ergodic Flocking Conan Veitch Duncan Render and Alex Aravind Abstract Designing effi cient control strategies is well stud ied Due to recent technological advancements and applications to the fi eld of robotics exploring ways to design optimal control for multi robot systems is gaining interest In this respect ergodicity has been successfully applied as an effec tive control technique for tracking and coverage Generating fl ocking behaviour is a problem with many interesting special cases that include both tracking and coverage The main contribution of this paper is the application of ergodicity to emulate fl ocking behaviour Our approach is appealing as control and communication are all assumed to be local and so this behaviour is self organized Simulation results show that the proposed approach is effective Keywords Ergodic optimization Flocking Decentralized control Localized communication Swarm robotics I INTRODUCTION The design and development of multi robot systems have been promoted in recent years as a consequence of rapid advances in sensing and embedded computing technologies A task that would be diffi cult for a single agent can instead be accomplished collaboratively by a distributed system of robots Distributed systems boast fl exibility are adaptable and are generally more robust than a system consisting of a single complex robot In the context of autonomous mobile multi robot systems it is then essential that the implementation of tasks for the system be robust reliable and above all scalable This requires a coordination between robot agents that communicate some notion of individual and group agent position while still acknowledging objectives and domain boundaries Two common primary tasks of multi robot systems are tracking of certain targets and coverage of a specifi ed area for applications such as search and rescue or mine sweeping The generic behaviour emerging from combining these two basic behavioural tasks is known as fl ocking Flocking is then the aggregation and group movement of a collection of agents often accomplished without agents having global information 15 23 Without global information each member of a system can only communicate via local interactions with neighbouring agents These interactions create global patterns and fl ocking behaviour emerges This fl ocking behaviour will often have global target direction or even an emergent direction 14 To achieve useful predictable fl ocking behaviour external instructions can be inserted into the system This work was partly supported by NSERC Discovery Grant RGPIN 2015 03761 Department of Computer Science University of Northern British Columbia Canada E mail conan veitch drender csalex unbc ca Three simple rules can be inserted into a multi robot sys tem algorithms to simulate fl ocking behaviour i Alignment each robot should attempt to match the velocity of its neighbours ii Cohesion each robot should attempt to move towards the average of positions of its neighbours and iii Collision avoidance each robot should avoid collision with other robots and obstacles by staying at a specifi ed proximity The traditional approach of embedding control logic into the algorithm directly to execute the above three rules in every step in addition to their main global tasks has limitations An alternate approach using ergodicity has been applied to the specifi c multi robot problems such as tracking and domain exploration 3 4 11 20 A persistent theme with ergodic systems is that they relate the time averaged behaviour of the states of a system to its set of total states the same behaviour is averaged over their domain as averaged over all of their states over time 7 Since each state in an ergodic system will eventually be reached we can use a measure of how ergodic an agent s trajectory is in order to effi ciently cover a domain A higher weighting can be given to areas in a domain that require exploration so that the agent s trajectory spends most of its time in these areas Indirectly this ensures that a agent does not spend time in subsets of a domain that do not need coverage allowing an agent to explore more effi ciently 5 These solutions use a centralized control that require global knowledge of the multi agent system That raises the following three basic questions 1 Can ergodicity be applied to achieve fl ocking be haviour of multi robots 2 If so how 3 Can the solution work without global control and knowledge ie Can the solution work with only local control and local knowledge These questions are answered affi rmatively in this paper The fl ocking behaviour being emulated in this work is a modifi cation of global direction The work provides a method for emulating fl ocking behaviour in a multi or swarm robot system that relies only on local information between robots It accomplishes this by extending the ergodic metric provided in 5 to require only local coeffi cient generation Rather than requiring each agent in a system to encode a fl ocking algorithm in the robots behaviours it relies only on generating an ergodic trajectory with a given spatial distribution Our method is simple robust and above all scaleable Paper organization Section II covers the basics of er godicity and its application to coverage and tracking Using 2019 IEEE RSJ International Conference on Intelligent Robots and Systems IROS Macau China November 4 8 2019 978 1 7281 4003 2 19 31 00 2019 IEEE6957 ergodicity to solve fl ocking is presented in Section III and its simulation is shown in Section IV The related work is reviewed in Section V and the paper is concluded in Section VI II ERGODICITY There are many applications for ergodic theory in the multi robot systems fi eld since it deals with the time averaged behaviour of dynamical systems For example a collection of robots covers an area ergodically if that area can be closely approximated by the states in the system trajectory formed by those robots over time This system can be called ergodic if the time average of the agents trajectory equals the average of all system states in the systems phase space if the fraction of time a trajectory spends in a subset of a domain is equal to the measure of that subset 1 In the case of a system like multi and swarm robotics we are concerned with approximating the phase space rather than equalling it A swarm trajectory consists of agents and a bounded domain As the agents move in discrete steps through a domain a system trajectory is generated In order to quantify how ergodic a trajectory is acting it is necessary to formulate a metric for ergodicity Such a metric was developed by Mathew and Mezic and provides a comparison tool for how well a trajectory is sampling a given probability distribution It does this by outputting a positive value that quantifi es how well the trajectory is covering the domain A value of zero implies that coverage is uniform and the trajectory is ergodic The metric is then used to inform the control of each agent in the system forcing each agent to move in such a way that the metric is minimized at each step Over a time t the goal of agent control is to have the metric vanish so that 0 as t In this way a multi robot system can cover any area in a domain based upon some probability distribution over that domain Each agents control inherently takes a provided distribution into account without the need for any secondary coverage algorithms A Ergodicity in R2 We assume that a robot agent is situated within a rectangu lar domain d defi ned as d L1 L2 where L1 0 L1 L2 0 L2 and where L1 L2 R A distribution x over d is assumed to be provided externally this distribution is generally application specifi c The function can be thought of as an information density over the domain and it is assumed that is zero at all points outside of d A robot in the system has position coordinates x d situated within R2so the set of all agent coordinates in a system at a given time step i is the systems state si where i 0 1 2 n A system trajectory x is the set of all siup to the current time step n The metric provided by Mathew and Mezic compares the distribution with the spatial statistics of x This metric decomposes both and x into Fourier coeffi cients It is important to note that this is one of many methods to achieve ergodic trajectories and as such is not strictly necessary in order to compute ergodicity This method signifi cantly reduces computational complexity however 5 6 8 To implement this metric both and x must be decom posed into Fourier coeffi cients The decomposition of into Qs i 1 Ki 1 coeffi cients k where k k1 k2 9 is k Z d x Fk x dx 1 where Fkis the Fourier basis function for vector k As our domain is in R2 our basis function is taken as 5 Fk x 1 hk cos k1x1 cos k2x2 where 2 k1 K1 L1 k2 K2 L2 and 3 hk sZ L1 0 Z L2 0 cos2 k1x1 cos2 k2x2 dx1dx2 4 The normalizing term hkensures that Fkis orthonormal since each entry will have unit length After computing our spatial distribution s Fourier coeffi cients we must do the same for the system trajectory To do so we create a probability density function c x from trajectory x c x 1 T Z T 0 x x t dt 5 where x t is the system state at time t is the Dirac Delta 5 and T Z a fi nite time horizon The Fourier coeffi cients of c x are given by ck x 1 T Z T 0 Fk x t dt 6 After decomposing our distributions into their respective coeffi cients we can then compare them in a metric of ergodicity x X k k ck x k 2 7 where kis a scaling factor k 1 a k 2 3 2 8 In this way quantifi es the difference between the trajec tory of a robot and the ideally ergodic trajectory that could be generated by the same system In order for the spatial average of the domain to approximate the time average of our trajectory as t T the control of each robot must minimize The above metric however only takes into account a single robots trajectory We need a way to measure multi robots trajectory 6958 B Multi robot Ergodicity In order to combine the trajectories of multiple robots in a swarm the trajectory coeffi cients of each individual robot are averaged For Narobots each agent has a individual trajectory x and xj n will be the corresponding state at time n of agent j We can then average the trajectory coeffi cients as 9 ck x 1 Na 1 N Na X j 1 N X n 0 Fk xj n 9 When these coeffi cients are considered in the metric the corresponding dynamics of each individual robot are inconsequential Each robot can have differing dynamics if necessary even though each robot will attempt to explore the closest area of high information density within the distribution as long as their control laws are informed by the metric The system will attempt to match the spatial average of the domains distribution with the time average of all of the robots Concern lies with having Naagents attempting to compute coeffi cients globally for this style of multi robot ergodicity to work Each agent must communicate their trajectory coeffi cients with all other robots This allows the robots to average every other robots coeffi cients in order to generate a unifi ed trajectory coeffi cient for the system as a whole In order to fi nd the average coeffi cients of the system each robot is required to broadcast their own trajectory coeffi cients receive the coeffi cients of all other robots then compute the system ck ckwhile ensuring that the computed value is the same as every other agents Having each agent receive all other agents trajectory coeffi cients before generating the average locally can have unintended consequences Coeffi cient loss due to obstacles multipath and weather fade shadow induced fading and connectivity between potentially wireless nodes 13 are all signifi cant challenges to a fully distributed multi robot model imple menting this style of ergodicity C Time Elapsed Distributions Time elapsed distributions are spatiotemporal distributions x t 12 that provides a spatial density x at a given time t This is accomplished by including a time parameter in our basis function Fk In R2 the basis function then becomes Fk 1 hk cos k1x1 cos k2x2 cos k3 t T 10 III ERGODICFLOCKING We consider strictly local communication between agent neighbours as a basic characteristics of fl ocking This charac teristics also makes fl ocking behaviour scalable Therefore to emulate scalable fl ocking using ergodicity we need i an aggregation of robots to one location and then ii tracking a given distribution as a group using only lo cal communication We achieve the two steps required for scalable fl ocking with three rules i Aggregate robots to one location using ergodic coverage ii use a time elapsed distribution and ergodic tracking to simulate fl ocking and iii use only local coeffi cient generation to inform ergodicity and neighbourhood communication This is described in Section D Local Coeffi cient Generation Using these ideas we implement fl ocking behaviour in two stages i Apply ergodic coverage by positioning a distribution at a desired initial location Each robot will cover that area ergodically clustering in and around and ii defi ne and deploy a time elapsed distribution to specify a fl ocking trajectory and let the multi robots exhibit ergodic tracking behaviour following the time elapsed distribution Two key aspects in achieving scalable ergodic fl ocking are effective trajectory generation and effective control and communication A Trajectory Generation A great deal of work has been done on trajectory gener ation 4 8 11 but most of these are computationally expensive and as such are not suitable to the low power microcontrollers common to multi robot systems A simple algorithm for trajectory generation called Spectral Multi Scale Coverage SMC with low computational cost is provided in 5 This algorithm generates trajectory steps quickly in real time although with a trade off of precision SMC covers a distribution very coarsely initially and covers more fi nely as time elapses This trade off is acceptable in multi robot fl ocking applications where the number of agents will make up for any initial loss in coverage SMC will only work for robot systems made up of single or double integrators and we describe the single integrator case below The feedback laws are intended to drive the metric to zero as quickly as possible by maximizing the rate of decay of the metric at each time step The feedback law is different pending on robot dynamics For single integrators 5 the feedback law for robot j at time t with maximum velocity umaxis uj t umax Bj t Bj t 2 and 11 Bj t tNa X k k ck t textbfk Fk xj t 12 where Fk x is the gradient vector fi eld of the basis function of our domain Fk Since our domain is R2 Fk x 1 hk k 1sin k1x1 cos k2x2 k2sin k1x1 cos k2x2 13 Before describing an algorithm for generating ergodic trajectories we briefl y discuss the benefi t of local coeffi cient generation using neighbourhood communication B Control and Communication The benefi t of multi robot ergodicity is the sharing of global trajectory distribution information to guide each robots next control step in optimizing the metric In multi robot ergodicity each robot does not have access to global coeffi cients and as such will be less effi cient with their 6959 time in exploring a domain than a robot that is part of a centralized system We observe that this loss of effi ciency is negligible over time in standard area coverage problems using ergodicity as will be shown in Fig 1 in the simulation section C Local Coeffi cient Generation and Collision In order to create a robust system that takes advantage of ergodicity in a scalable intuitive way we modify the averaging of trajectory coeffi cients Each robot within a group should communicate to only a local subset of the group This is both a useful and functional limitation placed on each member as each robot is typically very restricted in sensor capacity size and as an indirect result power Constant communication with all members of a group would require non direct transfer of information an expensive prospect We then modify the averaging of robot coeffi cients as follows rather than an average of every member of a group each robot received the coeffi cients of all members within a local neighbourhood This neighbourhood can be defi ned in any way natural to the system in question whether by communication hops physical distance or some other way Each robot is then free from being forced to synchronize with each other member of the group at each Ergodic fl ocking does not replicate the three rules of fl ock ing It instead replicates the desired behaviour of fl ocking by having a swarm of robots aggregate then uniformly cover a time elapsed distribution There is no inherent collision detection in the ergodic fl ocking algorithm but the swarm is still capable of avoiding one another during movement The robot system moves in a desired heading without dispersing due to the ergodic fl ocking algorithm While travelling as long as the distance traversed by a robot in a single time interval is strictly less than the local neighbour threshold distance of a robot the SMC feedback law ensures that no two robots generate the same coordinate at the same time step This means that no two robots will have the same goal coordinates at any given time step It is possible to approximate fl ocking behaviour with multi robot ergodic trajectories Typically a collection of algorithms or built in behaviours would be required to accomplish fl ocking behaviour in a multi robot system Ben efi cially ergodicity provides a stable framework for which collective group navigation can be performed without having to introduce additional algorithms Rather than having a large library of algorithms available to each robot it is preferable for each member of a multi robot system to take advantage of a navigation framework that can adapt pending situation or required task It is important to note that the fl ocking behaviours provided by a system of robots generating