# placing_influencing_agents_in_a_flock__f5704934.pdf

Placing Inﬂuencing Agents in a Flock

Katie Genter and Peter Stone Department of Computer Science, University of Texas at Austin Austin, TX 78712 USA {katie,pstone}@cs.utexas.edu

Flocking is a emergent behavior exhibited by many different animal species, including birds and ﬁsh. In our work we consider adding a small set of inﬂuencing agents, that are under our control, into a ﬂock. Following ad hoc teamwork methodology, we assume that we are given knowledge of, but no direct control over, the rest of the ﬂock. In our ongoing work highlighted in this abstract, we are speciﬁcally considering the problem of where to initially place inﬂuencing agents that we add to such a ﬂock. We use these inﬂuencing agents to inﬂuence the ﬂock to behave in a particular way - for example, to ﬂy in a particular orientation or ﬂy in a particular pattern such as to avoid an obstacle.

Introduction Flocking is an dynamic, emergent swarm behavior found in various species in nature. Each animal in a swarm follows a simple local behavior rule that results in a group behavior that often appears well organized and stable. In this abstract, we brieﬂy introduce some of our ongoing work on the problem of leading a team of ﬂocking agents in an ad hoc teamwork setting. An ad hoc teamwork setting is one in which one or more teammates which we call inﬂuencing agents must determine how to best achieve a team goal when given a set of possibly suboptimal teammates that we are unable to directly control or alter (Stone et al. 2010). As a motivating example, imagine that a ﬂock of migrating birds is ﬂying directly towards a dangerous area, such as a wind farm or an airport. Our goal is to encourage the birds to avoid the dangerous area without signiﬁcantly disturbing them. Since there is no way to directly control the ﬂight path of the birds, we must instead alter the environment so as to induce the ﬂock to alter their ﬂight path as desired. In our work, we assume that each bird in the ﬂock dynamically adjusts its heading based on that of its immediate neighbors. We assume that we control one or more inﬂuencing agents perhaps in the form of robotic birds1 or ultralight aircraft2 that are perceived by the rest of the ﬂock as one of their own. It is through these inﬂuencing agents that

Copyright c 2015, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved. 1www.mybionicbird.com 2www.operationmigration.org

we alter the birds environment so as to induce them to alter their path. Our previous work has considered how randomly placed inﬂuencing agents should behave so as to inﬂuence the ﬂock to face a particular direction or maneuver along a path so as to avoid an obstacle (Genter and Stone 2014). In our current research summarized in this abstract, we wish to examine how the inﬂuencing agents should be placed in the ﬂock. Speciﬁcally, we are considering: where should inﬂuencing agents be initially located within a ﬂock to maximize their inﬂuence on the ﬂock?

Problem Deﬁnition We use a simpliﬁed version of Reynolds Boid algorithm for ﬂocking (Reynolds 1987) in which each agent calculates its orientation for the next time step to be the average heading of its neighbors at the current time step. An agent s neighbors are the agents located within some set radius of the agent. In order to calculate its orientation for the next time step, each agent computes the vector sum of the velocity vectors of each of its neighbors and adopts a scaled version of the resulting vector as its new orientation. At each time step, each agent moves one step in the direction of its current vector and then calculates its new heading based on those of its neighbors. All agents maintain constant, identical speeds. Our domain is not a torus, so once agents leave the visible domain we consider them lost forever and irretrievable by inﬂuencing agents. The n agents that comprise the ﬂock consist of k inﬂuencing agents and m ﬂocking agents, where k +m = n. The inﬂuencing agents attempt to inﬂuence the ﬂock to travel in a pre-deﬁned direction we refer to this direction as θ . We conclude that the ﬂock has converged to θ when every agent that is not lost forever and is not an inﬂuencing agent is facing within 0.1 radians of θ .

Control of Inﬂuencing Agents In recent work we considered how to inﬂuence a large, nonstationary ﬂock to (1) quickly orient towards a target orientation and (2) maneuver through turns quickly but with minimal agents becoming lost as a result of these turns (Genter and Stone 2014). We introduced a 1-step lookahead algorithm for determining the individual behavior of each inﬂuencing agent. This 1-step lookahead algorithm considered

Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence

all of the inﬂuences on the neighbors of an inﬂuencing agent and allowed the inﬂuencing agent to determine the best orientation to adopt (where best is deﬁned as the behavior that exerts the most inﬂuence on the next step).

Maximizing Inﬂuence In our current work, we consider where to place k inﬂuencing agents in a ﬂock initially in other words, at the point the inﬂuencing agents begin inﬂuencing the ﬂock. In the following subsections we shortly discuss our base case, as well as the various approaches we are currently considering for initially placing the inﬂuencing agents.

Random Approach Our past research has randomly placed the inﬂuencing agents within the dimensions of the ﬂock (Genter and Stone 2014). Hence, we use random placement as the base case for evaluating our other placement approaches.

Grid Approach Grid placement places k inﬂuencing agents at predeﬁned, well-spaced, gridded positions throughout ﬂock. The placement of the inﬂuencing agents is dependent on the space covered by the ﬂocking agents, and not on the positions of ﬂocking agents and the actual grid size is dependent on k. In any particular grid, the inﬂuencing agents are spread out among the possible positions as much as possible.

Border Approach Our border approach works by placing k inﬂuencing agents as evenly as possible around the space covered by the ﬂocking agents. As in the grid approach, the placement of the inﬂuencing agents is not dependent on the positions of ﬂocking agents. Instead, we place inﬂuencing agents on each side of the ﬂock such that at most k

4 inﬂuencing agents are positioned on any particular side of the ﬂock. If more than one inﬂuencing agent is placed on a particular side of the ﬂock, the inﬂuencing agents spread out as much as possible on that side of the ﬂock.

Graph Approach The graph approach places the inﬂuencing agents such that the number of ﬂocking agents not connected to any inﬂuencing agent directly or indirectly is minimized. If multiple placements of inﬂuencing agents lead to minimal unconnected ﬂocking agents, then the graph approach attempts to maximize the number of direct or indirect connections between ﬂocking agents and inﬂuencing agents. This graph approach can be thought of as a graph connectivity problem, where each agent is a node and each set of neighbors are connected by an edge.

Preliminary Results We utilize the MASON simulator (Luke et al. 2005) for our experiments. In our experiments, we use each of the four methods discussed above to initially place the inﬂuencing agents and then the inﬂuencing agents behave according to the 1-step lookahead algorithm. Due to the limited length of

this abstract, we do not report the details of our experimental setup and we only present one set of preliminary experimental results. Figure 1 shows the average number of ﬂocking agents lost by the different approaches when n = 10. Note that the graph approach loses fewer ﬂocking agents than the other approaches for each of the ﬁve k s considered. This is because the ﬂocking agents are sparsely populated in the environment, and hence tend to have fewer neighbors. This is important because ﬂocking agents with few neighbors are less likely to be inﬂuenced by distant inﬂuencing agents. Additionally, the graph approach performs better than the other approaches when the percentage of inﬂuencing agents in the ﬂock is higher. This is because the graph approach focuses on minimizing the number of unconnected ﬂocking agents, so as a higher percentage of the ﬂock is composed of inﬂuencing agents, the number of unconnected ﬂocking agents decreases quicker for the graph approach than for the other approaches. Finally, note that no ﬂocking agents are lost by the graph approach when 50% of the ﬂock is composed of inﬂuencing agents. This is because the graph approach places the inﬂuencing agents such that each ﬂocking agent is inﬂuenced by at least one inﬂuencing agent.

Figure 1: The average number of ﬂocking agents lost across 100 trials.

Discussion Our ongoing work considers how inﬂuencing agents can best be placed into a ﬂock. We give a high-level overview of four approaches that could be used to place the inﬂuencing agents into the ﬂock, and provide one set of preliminary results on a small ﬂock of ten agents.

References Genter, K., and Stone, P. 2014. Inﬂuencing a ﬂock via ad hoc teamwork. In ANTS 14. Luke, S.; Ciofﬁ-Revilla, C.; Panait, L.; Sullivan, K.; and Balan, G. 2005. Mason: A multi-agent simulation environment. Simulation: Transactions of the Society for Modeling and Simulation International 81(7):517 527. Reynolds, C. W. 1987. Flocks, herds and schools: A distributed behavioral model. SIGGRAPH 21:25 34. Stone, P.; Kaminka, G. A.; Kraus, S.; and Rosenschein, J. S. 2010. Ad hoc autonomous agent teams: Collaboration without precoordination. In AAAI 10.