Shepherding Via Deformable Shapes

Shepherding via Deformable Shapes Joseph F. Harrison

Christopher Vo

Abstract— In this paper, we present a new motion planning strategy for shepherding in environments containing obstacles. This instance of the group motion control problem is applicable to a wide variety of real life scenarios, such as animal herding, civil crowd control, and oil-spill cleanup. The problem is challenging in terms of scalability and robustness because it is dynamic, highly underactuated, and involves multi-agent coordination. Our previous work showed that high-level probabilistic motion planning algorithms combined with simple shepherding behaviors can be beneficial in situations where low-level behaviors alone are insufficient. In this paper, we present a hybrid behavior called D EFORM, in which the shepherds view the flock as an abstracted deformable shape. We show that our method is more robust than our previous approach and that it scales more effectively to larger teams of shepherds and larger flocks.

Jyh-Ming Lien

(a)

(b)

(c)

(d)

I. I NTRODUCTION Group motion control is the problem of moving a group of agents in coordination. An instance of this problem is shepherding, where the objective is to herd a group of agents (e.g. a flock of sheep, crowd of people, etc.) using one or more “shepherd” agents (e.g. shepherds, riot police, etc.). The objective of shepherding is typically to guide the group to a goal, though other variants exist (e.g. escort or protection - a “parent” tries to maintain separation between their “child” and “stranger” [1]). A solution to the shepherding problem is usually a sequence of movements the shepherd can perform to guide the group to the goal. This sequence may be the output of a high-level motion planner, the result of agentbased behaviors working independently or in coordination to achieve high-level commands, or some combination thereof. Our recent work [2] showed that high-level planning combined with low-level shepherding behaviors can be an effective approach to guiding flocks amongst certain kinds of obstacles. However, the results were inconsistent, and on environments with narrow corridors and multiple paths to the goal, our simplest method, “Medial Axis GraphBased” (M AGB) outperformed the planning-based methods when given a fixed budget of simulation steps. However, M AGB does not scale well to larger flocks or larger teams of shepherds. Main results This paper introduces a new approach to shepherding called D EFORM, which is a hybrid of behaviorbased shepherd motions and low-level planning. The method relies on an abstraction of the flock as a discretized deformable shape or “blob”. We have chosen this abstraction All authors are with Department of Computer Science, George Mason University, 4400 University Drive MSN 4A5, Fairfax, VA 22030 USA,

{jharri1, cvo1, jmlien}@cs.gmu.edu

Snap shots (a-d) of 15 shepherds successfully herding a large flock with 200 members exhibiting simple flocking behaviors from one plaza to another in a street like environment. Fig. 1.

for several reasons. First, it more accurately represents the contour of the flock than simpler representations such as spheres or bounding boxes. Second, it favors areas of the search space where there is enough clearance for the blobs to pass through. Our experiments show that D EFORM broadly outperforms our previous method (M AGB) in terms of robustness (higher success rate), and scalability (effective for larger flocks and larger teams of shepherds). II. R ELATED W ORK The group motion control problem is one that merges the simulation and modeling of multi-agent dynamics with cooperation, planning, and control. There is a large body of work on the dynamics and modeling of human crowds, but there is still very little work on swarm motion control via agent interactions, and no work has been proposed to systematically study group motion control as a whole. Works that explore the crowd control problem have used a variety of simple approaches such as introducing new objects or agents into the environment. For example, the effect of adding barriers into disaster scenario environments

was studied in [3]. Other works have attempted to model the effect of adding agents with various social forces. The effect of adding robots with attractive social forces was examined in [4], and crowd dynamics in the presence of “leader” individuals was modeled in [5]. There are several works in robotics and computer animation related to modeling behaviors such as shepherding. For example, Schultz et al. [6] applied a genetic algorithm to learn rules for a shepherd robot. Its objective was to control the movement of other robots (sheep) that react by moving away from the shepherd. Vaughan et al. [7] simulated and constructed a robot that shepherds a flock of geese in a circular environment. In computer animation, Funge et al. [8] simulated an interesting shepherding behavior in which a T. Rex chases raptors out of its territory. Potter et al. [9] studied a herding behavior using three shepherds and a single sheep in a simple environment. None of the aforementioned methods have shown the ability to guide flocks in environments with obstacles. Swarm control can also be viewed as a cooperative problem. The survey from Parker [10] provides an overview of multi-robot systems. From the perspective of multi robot systems, the task of crowd control requires inherent cooperation, in which the success of a robot in the team depends on the actions of other robots. Inherent tasks (such as crowd control) are distinguished from non-inherent tasks (such as covering) in that they cannot easily be decomposed into independent sub-tasks and thus are generally more difficult. Multiple robots may also move in formation [11] to accomplish a given task. In our previous research on shepherding behaviors [12], we observe that formations can be used effectively to control the motion of the group. Similar observations have also been found in sociological studies of crowd control [13]. Recently, Shell and Matari´c [14] have used multiple robots to deploy and assist with the evacuation of pedestrians. Effective solutions to the shepherding problem might also be applicable in other areas. The deformable shapes used in this paper have dynamic properties similar to oil spills [15], and this approach may be useful for developing effective containment and cleanup strategies. Other Recent Work (note: integrate these into the other sections) Yeh et al. developed composite agents [1] which can exhibit many different behaviors including guidance, for which they use proxy agents as temporary obstacles. III. P RELIMINARIES A. Group Control Problem In this section, we define some of the terms and concepts that are used later in the paper. In a group control problem, there are two types of agents: shepherds C and a flock G. A shepherd is an external agent that influences the movement of the flock. A flock is a collection of agents that try to steer away from the shepherd. The shepherd’s task is to steer the flock to desired locations. All agents have the shape of 2-d discs (of varying radii). The state of an agent A (a shepherd or a flock member) is represented by the position and velocity of A, i.e., (xA , vA ).

Let the composite states of C at the time step t be SC (t) and let those of G be SG (t). Therefore, a group control problem with n flock members and m shepherds in a 2-d workspace will have a state space in 4(n + m) dimensions. Each flock member g ∈ G will be repelled by each visible shepherd c ∈ C. We assume that the shepherd c knows about g’s reactions. The flock G also exhibits certain behaviors when no shepherds are visible. In this paper, we will use the flocking behavior [16]; however, other models such as pedestrian dynamics [17] can also be used. In fact, the proposed methods will be independent of G’s behaviors. In addition to the collision-free constraint, other (user-defined) constraints may be added, such as constraints that prevent the flock from separating for too long or prevent merging different types of flocks. A state that does not violate any constraints is called a feasible state. We use the term target to denote any intermediate position that the shepherd attempts to steer the flock towards, and we use the term steering point to denote any position to which the shepherd moves himself in order to influence the movement of the flock. A roadmap is an abstract representation of the feasible configuration space in a given environment, given as a directed graph G = (V, E), where each node in V represents a valid configuration, and each directed edge (p, q) ∈ E denotes that it is possible for the flock to travel from configuration p to configuration q. B. Problem Statement Finally, we define the group-control problem as follows: Given SC (0) and PG (0), find a sequence of feasible states SC (t) for 0 < t ≤ 1 so that all PG (t) are feasible and PG (1) ∈ GS, where GS is a set of user specified goal states. IV. OVERVIEW OF O UR M ETHOD In this section, we will talk about the main framework of the proposed method. This framework can be realized in many different ways. An implementation of this framework is discussed in Section V. A. Group Control as Deformable Shape Manipulation In order to control the flock’s motion, the shepherd’s internal models should comprise the following components: (1) the shepherd’s behavior model, (2) the environment model, (3) the flock model, and (4) a model to represent the other shepherds. Later, we will use these models as our basis to define shepherd’s motion. Details of each model are described below. Behavior model The shepherd’s behavior is similar to that of a single- or multiple-arm robot performing object manipulation. To manipulate an object, a robot arm must alternate between two basic behaviors: “Transit” (reaching and grasping the object) and “Transfer” (transporting the grasped object) [18], [19]. The shepherd has two analogous behaviors: “Approach” (transit) and “Steer” (transfer). In approaching behavior, the shepherds attempt to get close to the flock without disturbing it. In steering behavior, the shepherd attempts to move the flock.

obstacle

(a)

(b)

(c)

Fig. 2. (a) An environment with a global roadmap, two obstacles, a shepherd (larger disc) and two sub-flocks. Each flock member is shown as a small disc enclosed in a dashed circle, which represents its visibility. (b) The shepherd’s flock model is shown as two α-shapes for the two sub-flocks. (c) A local roadmap is built around the flock nearest the shepherd.

Environment model All shepherds have access to a global roadmap representing the workspace. An example of such a roadmap is shown in Fig. 2(a). Flock model It is impractical to handle each flock member individually, even when controlling a small flock. We believe that the shepherd should have a high level representation of the flock to more efficiently guide the flock. In most existing methods, a bounding circle of the flock is used to model the flock. This model works fine when the workspace is relatively sparse. However, in environments with many obstacles or narrow corridors or when the flock size is large, a bounding circle is excessively restrictive. In the proposed framework, the shepherd represents the flock as a deformable object which can also split and merge. During steering, the shepherd acts as a “deformer”, continuously reshaping the contour of the flock to some target shape. For example, the shepherds can represent the contour of the flock using α-shape [20], [21], shown in Fig. 2(b), which is updated as the flock moves. To prevent the shepherd from disturbing the flock unnecessarily, the value of α can be determined from the flock’s sensing range. In this paper, the shepherds represent the flock using “pixel blobs” (see Section V for details) to represent the flock’s deforming contour. Shepherd model A shepherd needs to have a model to represent other shepherds. This model affects how we solve the the task allocation problem that assigns steering positions to shepherds. In this framework, we use a centralized system that knows the locations of all the shepherds. This is analogous to a large robot arm with many fingers (i.e. shepherds) manipulating a deformable object (i.e. flock). All these fingers are connected to and only communicate with a central command center, which coordinates the shepherds. Therefore, we reduce the task assignment problem to a bipartite matching problem between the steering points and the shepherds. Then, the edge weight of the bipartite graph is the geodesic distance (estimated using the global roadmap) between a shepherd and a steering point. B. Shepherding By representing the flock as a deformable object, the shepherding problem becomes a deformable object manipulation

problem. Given a desired shape, the shepherds’ task is to find and position themselves at the contact points near the deformable object. A solution to the problem is likewise reduced to determining a sequence of target shapes that will eventually lead the flock to the final goal. D EFORM, shown in Algorithm 1, outlines the steps necessary to achieve the goal. Algorithm 1 D EFORM (G, C, g) Input: G (flock), C (shepherds), and g (goal) while g is not reached do Compute the contour polygon PG (t) of G at time t Determine the next target polygon PT (t + δt) Find ssteer ∈ SC to morph PG to PT Move C to ssteer More precisely, D EFORM regards the flock as a deformable object with an area conservative constraint. That is, D E FORM will find a sequence of continuously deforming polygons PG (t), t ∈ [0, . . . , 1], so that PG (1) is near a goal. For each PG (t), the shepherds can tightly pack all flock members in PG (t). Because D EFORM may not consider shepherd positions when building PG (t), additional soft constraints on PG (t) should be imposed to increase the chance of finding a successful control plan. For example, the shepherds should keep each polygon PG (t) as “fat” as possible and keep the medial or the principal axis of PG (t) close to the edges of the global roadmap. The fatness increases the controllability of the flock and the centeredness reserves room for maneuver. There are many ways to compute the target polygons PT (t). For example, we can grow a search tree along the edges of the global (workspace) roadmap. Alternatively, we can simply extract a path with maximal clearance and build a sequence of area-conserving polygons along the path. Details are discussed in the next section. Next, D EFORM computes the movements for the shepherds so that the flock can assume the shape of polygon PG (t) at each time step t. More specifically, given the desired shape PT (t + 4t) in the next time step and the current flock model PG (t), the behavior will determine the necessary deformation and transformation to morph PG (t) to PT (t + 4t) using, for example, the Iterative Closest Point

(ICP) algorithm [22] when α-shape is used to compute the contour. In this paper, we use boolean operators between pixel blobs to determine the necessary deformation. Finally, D EFORM calculates a steering state ssteer ∈ SC for the shepherds (recall that SC is the state space of the shepherds). a potential steering point

PG − PT

PT (a)

(b)

Fig. 3. (a) Target shape, current flock blob, and a potential steering point. (b) Finding steering points using a radial partitioning.

V. I MPLEMENTATION D ETAIL In this section, we flesh out the framework discussed in the previous sections. In particular, we discuss in detail how a flock is represented as a deformable shape, how the target shape is determined, and how the steering points are chosen. An important feature of our framework is that it can be implemented in many different ways. While using α-shapes can provide high accuracy in flock contour representation, in order to efficiently create the flock model, a new algorithm to efficiently update the α-shapes [23], [24], [25] is required. This method will need to exploit the temporal and spatial coherence of the flock’s movement. To avoid this difficulty, we discritize the workspace into a regular grid and represent the contour of the flock using pixel blobs (described below). Each cell in the grid is classified as a free cell if a flock member in the cell is free of collision from the workspace obstacle. Otherwise, the cell is marked as an in-collision cell. The size of the cell in the grid is defined by the geometric size of an individual flock member. Therefore, each cell can only be occupied by a single flock member. This approximation is very easy to implement and is very efficient (linear to the flock size). As we will see later in our experiments, this representation is also accurate enough to model and handle large flocks. A. Flock Blobs The pixel blob of a single member g of a flock is simply the set of pixels that are within the distance r − of g, where r is the sensor range of g and  is an arbitrarily small number. The pixel blob of a flock (called flock blob) is therefore the union of all pixel blobs of its members. The flock blob may have several connected components if the flock has separated into sub-flocks.

B. Target Blobs Given the current flock blob, the target shape is defined as another pixel blob, called a target blob, that includes all flock members at the next time step. It is straightforward to compute the target blob. First, we pick a pixel that is occupied by the closest flock member to the final goal position. The closeness to the goal is measured by geodesic distance. Once the center pixel o is determined, we grow the blob using free pixels, starting with the 8-connected set and expanding in concentric rings around o. We stop when the blob contains the same number of pixels as the number of flock members. This ensures that the blob is large enough to contain all flock members and also conserve the area of the target blobs throughout the entire control behavior. We say a flock configuration conforms to a target blob if the target blob includes all flock members. Note that the target blob could be grown in many different ways. For example, one could make it grow away from obstacles or toward the medial axis. The version we used in this paper makes the blob grow as fat as possible. C. Shepherds’ Steering Points Given a flock blob PG and a target blob PT , we compute the set of steering points ssteer . To compute ssteer , we first compute the differences between PG and PT . This is simply done by performing the boolean difference PG − PT pixel by pixel. Next, we determine a set of potential steering points, s0steer . We say a pixel p is in s0steer if (1) p is neighboring (using 8-connectivity) to a pixel c ∈ PG − PT , (2) p 6∈ (PG ∪ PT ), and (3) p is on the opposite side of the pixel in PT closest to c. An example of p is shown in Fig. 3(a). Once the points in s0steer are identified, the last step is to choose n points from s0steer , where n is the number of shepherds. If the there are fewer than n points in s0steer , we are finished. In this case, some shepherds may not have steering points assigned and will stay stationary. If there are more points in s0steer than there are shepherds, then we partition s0steer into n pie wedges whose apex is at the center of PT (the flock member closest to the global goal). In each pie wedge, the point in s0steer farthest from the global goal is selected as a steering point (see an example in Fig. 3(b)). After ssteer is computed, the steering points are assigned to the shepherds by forming a bipartite graph whose nodes are the points in ssteer and the shepherd positions, and whose edge weights are geodesic distances between them. The steering point assignment is then solved using a bipartite matching algorithm. Screen shots our simulation running D EFORM can be found in Fig. 4. VI. B EHAVIOR - BASED M OTION P LANNERS D EFORM can also be used as a local planner in higherlevel planners such as PRM, RRT and EST. Based on our results here and in [2], planning is not generally helpful.

potential steering points

shepherds

Fig. 4.

PG − PT

PT

flock

(a) “empty”

(b) “s”

(c) “spiral”

(d) “broken-t”

(e) “pillars”

(f) “env-6”

Screen shots of the proposed shepherding behavior in action.

However, theoretically speaking, the proposed control behavior may not always successfully control the flock. For example, in some rare cases, the deformable polygon may block paths needed by shepherds to reach their steering points. For the sake of completeness, we will discuss two high-level planners: RRT and META - GRAPH integrated with the D EFORM. A. Distance Metrics In both planners, distance metrics are important for estimating the the probability of successfully herding from one flock state to another flock state. Using Euclidean distance is usually not enough to reflect this probability. In addition, we use the idea of deformation energy which defines the amount of effort needed to deform one polygon (representing the start state) to another polygon (representing the goal state). Again, deformation energy can be implemented in many ways depending on the representation of the deformable object. By representing the polygon as a pixel blob, we have the advantage of efficiently computing the overlay of two deformable polygons. More specifically, given two pixel blobs, P and Q, we translate P so that their centers coincide, then count the number of pixels in the boolean difference P −Q. This value approximates the number of pushes needed to deform P to Q. The final distance between P and Q is simply a weighted sum of the Euclidean distance between their centers and the deformation energy estimated by boolean difference P −Q. In our implementation, we use the same weights for both Euclidean distance and deformation energy. B. RRT Our RRT-based planner constructs the roadmap G by repeatedly attempting to extend G using the proposed control behavior towards new randomly generated configurations in W . For RRT, the procedure S ELECT-I NTERMEDIATE G OAL chooses a random configuration g in the workspace, and the procedure S ELECT-N ODE -T O -E XPAND chooses the node already in G that is closest to g. C. Meta Graph Meta graph is a PRM-based method proposed in our recent work [2]. Although originally designed for directed circles,

Fig. 5.

Environments used in our experiments.

it can be easily adapted to the proposed method. Each node in a meta graph represents a meta configuration. A meta configuration defines a set of group configurations (excluding the shepherd positions) that are conforming to the properties of the node. More specifically, each meta configuration C is as a pixel blob that has twice as many pixels as the number of flock members. Each meta configuration intuitively defines a set of conforming flocks. We say a flock is conforming to a meta configuration C if x% flock members overlap with the pixels of C. In our implementation, we let x = 85. A meta configuration is generated in the same way as the target blob is generated (in Section V). We first pick a random point p in workspace and use p two grow a blob level by level. These meta configurations are then connected to their k-nearest neighbors form a meta graph. In a similar fashion to lazy PRM approaches [19], paths from the meta graph are extracted and evaluated using the proposed control behavior until a path is found, or until no path can be found to connect the start and the goal configurations in the meta graph. VII. E XPERIMENTAL R ESULTS We evaluated our new D EFORM behavior against the simpler M AGB behavior across 6 different test environments, shown in Figure 5. The next sections explain our experimental method. For this paper, each experimental sample consists of 30 runs, and claims of statistical significance are based on 95% confidence. A. Scalability We presume that increasing the size of the flock should impact both the effectiveness and performance of the shepherding algorithm, and that more shepherds will be needed to move larger flocks to the goals in a timely manner. The scalability of these behaviors is defined by the ability for them to effectively herd increasingly large flocks to the goal within the given simulation time budget. To test our hypotheses, we ran experiments with varying number of shepherds (1, 2, 3, and 4) and varying flock sizes

randomness. In these figures, randomness is shown as a ratio from 0.0 to 1.0 where 0.0 represents fully determinstic behavior and 1.0 represents fully random behavior. In general, D EFORM performs significantly better than M AGB with increasing flock randomness. An interesting effect is shown in Figure 7, where there is a bump in performance with increasing flock randomness for the M AGB behavior. We believe that this is because the random oscillation of the flock members helps the shepherds push them through narrow corridors in the broken-t environment in similiar way to salt through the openings of a salt-shaker.

DEFORM MAGB

1.2 1 Success Rate

0.8 0.6 0.4 0.2 0 -0.2

1

Success rate vs. Shepherd/Flock Ratio on s Environment.

(5, 10, 15, 20, and 25) on each of the 6 test environments. We computed success rates as the proportions of sample runs where the algorithm successfully moved the flock to the goal. Table I shows example results for the “brokent” environment. For small flock sizes, D EFORM and M AGB perform similarly. However, as the size of the flock increases, M AGB shows significant decay in performance - it is clear that more shepherds are needed to control larger flocks using the M AGB behavior. On the other hand, D EFORM manages to achieve excellent results throughout (above 90% sucess rate) with no negative trend in performance up to 25 flock members.1 We also ran experiments to test larger shepherd and flock sizes on the “s” environment. The results, shown in Fig. 6, show that D EFORM once again outperforms M AGB across the board, but especially with larger flock sizes. TABLE I

Flock Size

S UCCESS R ATES FOR D EFORM AND M AGB WITH VARYING S HEPHERD AND F LOCK S IZES (B ROKEN -T)

5 10 15 20 25

1 0.93 1.00 1.00 1.00 1.00

D EFORM # Shepherds 2 3 1.00 0.90 0.93 0.93 1.00 1.00 0.97 1.00 1.00 0.97

4 0.83 0.93 0.93 0.90 0.97

1 0.90 0.56 0.47 0.07 0.00

M AGB # Shepherds 2 3 1.00 0.93 0.97 1.00 0.80 0.77 0.67 0.43 0.40 0.33

DEFORM MAGB

1.2

8/40

Success Rate

Fig. 6.

4/20 6/30 Shepherd/Flock Ratio

0.8 0.6 0.4 0.2 0 -0.2 0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

Flock Randomness Fig. 7. Success Rate vs. Randomness Ratio on the broken-t Environment.

DEFORM MAGB

1.2 1 Success Rate

1/05 2/10

0.8 0.6 0.4 0.2 0

4 0.97 0.97 0.83 0.83 0.43

B. Robustness We define robustness as the ability for the shepherds to control the flock in spite of unpredictable flock behavior. We modeled the unpredictable behavior by linearly mixing each flock agent’s behavior with a random vector. We control this randomness by increasing and decreasing the magnitude of the random vector. Figures 7 and 8 illustrate the results (with 95% confidence bars) of success rate versus increasing 1 We intend to extend these experiments to higher flock sizes for the final release of this paper.

-0.2 0

Fig. 8.

0.1

0.2 0.3 0.4 0.5 Flock Randomness

0.6

0.7

Success Rate vs. Randomness Ratio on the s Environment.

C. Does High-Level Planning Benefit from D EFORM? Our previous work compared the effectiveness of a simple behavior-based shepherding algorithm to algorithms that combined low-level behaviors with high-level planning. We found that in many cases, the planning methods we applied did not yield significant enough improvements to justify the additional computational expense. Indeed, our tests showed that with a fixed budget of simulation steps, planning-based approaches using these techniques were often unable to even match the performance of our behavior-only method. In almost all environments, planners using the D EFORM

behavior performed significantly better than planners using the M AGB behavior. We are still studying how to make use of these shepherding behaviors with higher-level planners for better performance in difficult environments.

Environment

TABLE II S UCCESS R ATES FOR D EFORM AND M AGB W ITH VARIOUS H IGH -L EVEL P LANNERS AND E NVIRONMENTS

broken-t empty env6 pillars s spiral

None 0.97 1.00 1.00 0.97 0.97 0.83

D EFORM Planner Graph 0.13 0.00 0.30 0.96 1.00 0.70

Tree 1.00 0.77 0.97 1.00 0.83 0.53

None 0.86 1.00 0.10 0.93 0.70 0.00

M AGB Planner Graph 0.00 0.00 0.00 0.00 0.00 0.00

Tree 0.07 0.33 0.00 0.00 0.00 0.00

VIII. C ONCLUSION AND F UTURE W ORK This paper introduces and applies a new type of abstraction to the problem of shepherding. By representing the flock configuration as a discretized deformable object, we show that shepherding can be done more effectively than our previous best method [2] in terms of handling larger flock sizes and unpredictable flock behavior. This algorithm also has the virtue of needing less information about the environment. Whereas our previous method relied on the medial-axis of the map, this new algorithm needs only an occupancy grid indicating open and closed tiles. This makes it significantly more applicable to robotics scenarios where a priori map information is not available. In the future, we’d like to try growing target blobs that favor metrics besides just “fattest”, such as growing away from obstacles or towards planned waypoints. We are also further exploring the interaction between high level planning and these behaviors. R EFERENCES [1] H. Yeh, S. Curtis, S. Patil, J. van den Berg, D. Manocha, and M. Lin, “Composite agents,” in Proceedings of Eurographics / ACM SIGGRAPH Symposium on Computer Animation, M. Gross and D. James, Eds., 2008. [2] C. Vo, J. F. Harrison, and J.-M. Lien, “Behavior-based motion planning for group control,” in Proceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS), St. Louis Missouri. To Appear., 2009. [3] M. Brenner, N. Wijermans, T. Nussle, and B. de Boer, “Simulating and controlling civilian crowds in robocup rescue,” in Proceedings of RoboCup 2005: Robot Soccer World Cup IX, 2005. [4] J. Kirkland and A. Maciejewski, “A simulation of attempts to influence crowd dynamics,” in IEEE International Conference on Systems, Man and Cybernetics, vol. 5, 2003, pp. 4328–4333. [5] F. Aub´e and R. Shield, “Modeling the effect of leadership on crowd flow dynamics.” in ACRI, ser. Lecture Notes in Computer Science, P. M. A. Sloot, B. Chopard, and A. G. Hoekstra, Eds., vol. 3305. Springer, 2004, pp. 601–621.

[6] A. C. Schultz, J. J. Grefenstette, and W. Adams, “Robo-shepherd: Learning complex robotic behaviors,” in In Robotics and Manufacturing: Recent Trends in Research and Applications, Volume 6. ASME Press, 1996, pp. 763–768. [7] R. T. Vaughan, N. Sumpter, J. Henderson, A. Frost, and S. Cameron, “Experiments in automatic flock control,” J. Robot. and Autonom. Sys., vol. 31, pp. 109–117, 2000. [8] J. Funge, X. Tu, and D. Terzopoulos, “Cognitive modeling: Knowledge, reasoning and planning for intelligent characters,” in Computer Graphics, 1999, pp. 29–38. [9] M. A. Potter, L. Meeden, and A. C. Schultz, “Heterogeneity in the coevolved behaviors of mobile robots: The emergence of specialists,” in IJCAI, December 2001, pp. 1337–1343. [10] L. E. Parker, “Current research in multi-robot systems,” Journal of Artificial Life and Robotics, vol. 7, 2003. [11] T. Balch and R. Arkin, “Behavior-based formation control for multirobot teams,” IEEE Trans. Robot. Automat., vol. 14, no. 6, pp. 926– 939, 1998. [12] J.-M. Lien, O. B. Bayazit, R.-T. Sowell, S. Rodriguez, and N. M. Amato, “Shepherding behaviors,” in Proc. IEEE Int. Conf. Robot. Autom. (ICRA), April 2004, pp. 4159–4164. [13] R. Applegate, Riot control: materiel and techniques. Stackpole Books, 1969. [14] D. A. Shell and M. J. Matari´c, “Directional audio beacon deployment: an assistive multi-robot application,” in Proc. IEEE Int. Conf. Robot. Autom. (ICRA), 2004, pp. 2588–2594. [15] X. Chao, N. J. Shankar, and H. F. Cheong, “Two- and three-dimensional oil spill model for coastal waters,” Ocean Engineering, vol. 28, no. 12, pp. 1557 – 1573, 2001. [Online]. Available: http://www.sciencedirect.com/science/article/B6V4F43MKKTY-3/2/26621349ce0865179e08c508afb58f69 [16] C. W. Reynolds, “Flocks, herds, and schools: A distributed behaviroal model,” in Computer Graphics, 1987, pp. 25–34. [17] P. Kachroo, S. J. Al-nasur, S. A. Wadoo, and A. Shende, Pedestrian Dynamics: Feedback Control of Crowd Evacuation. Springer, 2008. [18] Y. Koga, K. Kondo, J. Kuffner, and J. Latombe, “Planning motions with intentions,” in Proc. ACM SIGGRAPH, 1995, pp. 395–408. [19] C. L. Nielsen and L. E. Kavraki, “A two level fuzzy PRM for manipulation planning,” IEEE/RSJ International Conference on Intelligent Robotics and Systems, pp. 1716–1722, 2000. [20] H. Edelsbrunner, D. G. Kirkpatrick, and R. Seidel, “On the shape of a set of points in the plane,” IEEE Trans. Inform. Theory, vol. IT-29, pp. 551–559, 1983. [21] H. Edelsbrunner and E. P. M¨ucke, “Three-dimensional alpha shapes,” ACM Trans. Graph., vol. 13, no. 1, pp. 43–72, Jan. 1994. [Online]. Available: ftp://cs.uiuc.edu/pub/edels/geometry/shapes-94.tar.Z [22] P. J. Besl and N. D. McKay, “A method for registration of 3-d shapes,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 14, no. 2, pp. 239–256, 1992. [23] H. Cheng, H. Edelsbrunner, and P. Fu, “Shape space from deformation,” in PG ’98: Proceedings of the 6th Pacific Conference on Computer Graphics and Applications. Washington, DC, USA: IEEE Computer Society, 1998, p. 104. [24] S.-W. Cheng, H. Edelsbrunner, P. Fu, and K.-P. Lam, “Design and analysis of planar shape deformation,” Comput. Geom. Theory Appl., vol. 19, pp. 205–218, 2001. [25] H.-L. Cheng, T. K. Dey, H. Edelsbrunner, and J. Sullivan, “Dynamic skin triangulation,” in SODA ’01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2001, pp. 47– 56.