Pursuit and Evasion Techniques
supported by NSF
Samuel Rodriguez, Robert Salazar, Phillip Coleman, Jory Denny, Nancy M. Amato

We are interested in simulating various manners in which groups of agents can interact with each other. To this extent, pursuit and evasion is a commonly studied interaction. In this scenario, the participants are divided into two groups--the pursuers and the evaders. The pursuers seek to locate the evaders, and then capture or drive them towards a certain location. The pursuit may have the purpose of catching for food, apprehending a criminal, or herding the other agents to a desired goal location. The evaders attempt to avoid the pursuers, and if discovered or approached may attempt to escape the pursuers by running and hiding, or performing some other action to attempt to make the pursuer give up on chasing it. In our work, we combine our roadmap-based behaviors with an agent-based implementation. We use a framework that allows us to implement various behaviors by extending a general behavior algorithm. By changing different parameters in each of the behaviors or in the pursuers and evaders, we can control how the agents interact with each other and tune the manner in which the simulations progress as time passes. In the majority of the simulations, there is group of pursuing agents and one group of evading agents. We are also able to simulate multiple groups of pursuers and evaders, which may only be interested in specific groups in the environment rather than all evaders or pursuers. Furthermore, we have the ability for a group of agents to pursue a second group of agents, while simultaneously attempting to avoid a third group.

Evading Behaviors Our general evasion algorithm includes actions that an evader may take when attempting to escape from a pursuer. The evasion strategy has four stages: determining a threat, creating a defensive plan, acting upon the plan and adapting the plan. Particular evasion behaviors specialize the various stages of the General Evasion Algorithm. These behaviors can be characterized as to whether the agents have memory and if they can communicate with other agents. For example, the evading agent's behavior might be based solely on the pursuing agent(s) that are currently visible to it, or the evader's reaction might also be based on its memory of pursuing agents that it has seen, but can no longer directly observe. Evading agents may also have the option of communicating their knowledge of pursuing agents to other evading agents. In our current evasion behaviors, this information includes the last known locations of pursuing agents and a distance from those locations in which an evader might be detected by the pursuer; these locations and distances identify unsafe regions where evaders might be visible to pursuing agents. An example of how our hiding agents use memory can be seen in this animation. We have currently implemented two evasion strategies: flee-and-freeze and flee-and-hide. The flee-and-freeze strategy has the evaders stay at their current location until they are discovered, and then they will flee to another location and then freeze in place again. The flee-and-hide strategy is similar to the way humans play a game of hide-and-seek, where the hiders will attempt to position themselves in areas where they will remain undetected and if seen continue to try to evade pursuing agents. Flee-and-Freeze The strategy that the hiding behavior uses to attempt to evade pursuit directs the agents to remain in their current location while undetected. Once the evader knows that it has been detected, it will flee to what it believe is a safer location. At this new location, it will again stay still. Once the agent has determined the location to which it will flee, it will select a path to that location. The paths created will be evaluated based on the current knowledge of the other agents in the environment, and paths that are decided to be too risky will be rejected. Once a suitable path is found, the agent will begin moving towards its new location. However, the path selected may become less desirable due to encounters with other, previously unknown agents as time progresses. As such, the agent will need to evaluate the necessity for evasive action as it moves along its path. This behavior also has the capability to use memory and communication to enhance the ability to avoid pursuers. Movie(mpg): Flee-and-Freeze in Clearing-in-forest environment Flee-and-Hide The flee-and-hide strategy attempts to reduce the likelihood of being or staying visible to opposing agents. In this behavior, an agent generates points or hiding locations within its visible area. These points are then evaluated, or scored; different scoring functions are used depending on whether or not pursuers are present. A new hiding location can then be selected if one is found such that the score of the new location achieves some predefined percentage increase over the score of the current hiding location being used. The new goal and path are updated if a point is found that sufficiently improves the score. Although there are many ways to generate a score for hiding locations, we present two scoring strategies. These strategies are dependent upon whether or not the hiding agent is detected. When undetected, an agent will generate points within its visible radius, and check for visibility with those other points. When the agent has been detected, hiding locations generated will be scored based on the distance from the seeking agents, with points that are farther away being scored higher. The score will then be scaled, by a factor from 0 to 1, depending on the angle created by the position being evaluated, hiding agent and pursuing agent. If the hiding agent must move towards the pursuing agents, the score of the point will be drastically scaled down (resulting in a low score). A point that is in a direction away from the pursuing agent will have less scaling down of the score depending on the direction. This scoring strategy leads the hiding agents to prefer points that are both farther from the seeking agents and in a direction away from them. Both of these scoring strategies are easily adapted to take into account the memory and communication of potential areas where pursuing agents may be. This behavior also has the capability to use memory and communication to enhance the ability to avoid pursuers. Movies(mpg): Flee-and-Hide Basic in Forest-like environment Flee-and-Hide with agents having memory in Forest-like environment Flee-and-Hide with agents having memory in Forest-like environment Flee-and-Hide with communication between agents in Forest-like environment Pursuing Behaviors Our general pursuit algorithm outlines a basic pursuit strategy. This algorithm has four stages: location of the target, creation of a pursuit plan, acting upon the plan, and then ending the pursuit under a success or failure condition. Various strategies employ different customizations of the steps in the general algorithm. Furthermore, the agents may use any degree of cooperation with the other pursuing agents, ranging from independent actions to coordinated actions with the goal of increasing the chance for another agent to capture the evading agent. Our current behaviors support notification of the location of evading agents to other nearby pursuing agents and the coordination of starting positions of an attempt to capture an evading agent. Finally, the determination of whether or not a chase has failed may be an individual or collaborative decision among the pursuing agents. We currently have implemented two different pursuing strategies: basic pursuit and surround-and-attack. The basic pursuit will chase a target in a direct path until it either captures the target or the target is no longer visible. Agents employing this strategy have the option to either act by themselves or to relay the location of a target to nearby agents in its group. The surround and attack behavior requires a higher degree of cooperation from the pursuing agents. The pursuers will take up encircling positions and block off routes of escape for their intended prey before they commence their attack. For our strategy, once these location-based preparations are completed, the strategy for chasing the target is the same as with the basic pursuit. Basic Pursuit The most basic of the pursuit behaviors is simply to chase the target once it has been determined. The agents will search the environment for a target, and once found, will create and implement a plan of a direct chase. The pursuer will continue to chase the target until it has either caught the target or it is no longer able to track the target. The agents have the option to either act by themselves, or to relay the location of a target to nearby agents in its group. This communication allows agents to begin chasing a target from further away, and results in multiple agents chasing a single target. Movies(mpg): Basic Pursuit in an indoor maze-like environment Basic Pursuit in Clearing-in-forest environment Basic Pursuit with communication in Clearing-in-forest environment Basic Pursuit with communication in a forest-like environment Surround and Attack The motivation for surrounding the target is to block paths by which the target could potentially escape. The size of the pursuing group is specified as a parameter, and can be tuned to match the type of prey. For example, a larger prey for a group of smaller predators would require a larger group size for the pursuit. When enacting this behavior, the agents must focus on their current pursuit. As such, there is a list of agents that are not currently engaged in a pursuit, and are available to participate should a new pursuit commence. Once a target is located, the locating agent will form a subgroup of the surround and attack agents that will participate in the new pursuit. The size of the group is determined by two factors - the desired size of the pursuit subgroup, and the number of agents available to participate in a new pursuit. In the case that the desired number of agents are not available for a new pursuit, the pursuit group will consist of all of the remaining agents. There is also a preference to include agents who are nearby rather than agents that are distant. The agents must then determine how they will surround their target. The agents will decide upon locations encircling the target, which will use an estimated reaction distance. This is the distance at which the pursuers believe that the target will begin taking action based upon the presence of the pursuers. Therefore, the surrounding locations will need to be further from the target than this reaction distance. The agents also determine which agent will proceed to each location. Once these factors are decided, the agents will attempt to find a path from their current locations to their specified surrounding positions. These paths will also make use of the estimated reaction distance of the target, and will attempt to create their paths such that they remain far enough away from the target to prevent a reaction. There are two conditions that can cause the agents to begin chasing the target. The first is if the pursuing agents have all reached their surrounding locations. In this case, the preparations for the chase have been completed, and the pursuing agents should have the advantage of their positioning. The second condition is that the target moves to a location that is close to one of the surrounding agents. In this case, the agents will determine that there is a chance for an immediate capture, and will attempt to take advantage of the opportunity. Movie(mpg): Surround and Attack in Clearing-in-forest environment Behavior Combination for Pursuit and Evasion The above behaviors focus solely on either pursuit or evasion. However, it may be that an agent wishes to accomplish more than simply pursuing or evading another group of agents. In this case, there must be some form of arbitration between the different objectives and behaviors that the behavior possesses. Here, we have implemented two such methods of arbitrating between different behaviors. The first is a basic selection between the different behaviors. The agent will consider the observed state of the environment and its own internal state, then make a decision as to which of the available behaviors best suits the situation. In the second, the agent will have a main behavior that it will employ, and it will modify its planned path based on the objectives of the secondary behaviors. Behavior Selection The simplest method of handling multiple behaviors is to simply select one behavior to employ at a given time. The selection-base approach that we employ here decides which behavior should be active based upon the current state of the agent or group of agents. The following movies provide a demonstration of the selection-based behavior combination. For this setup, we use two groups of agents. For the first, we blend our patrolling behavior with our surround-and-attack behavior. The second behavior uses our foraging behavior with the flee-and-hide behavior. In the various scenarios demonstrated, the groups of agents are given different view ranges. The priorities are set so that when an agent in the first group detects an agent in the second group, it will switch to the surround-and-attack behavior. Agents in the second group will switch to a hiding behaivor when they notice an agent in the first group, but will quickly resume foraging once they lose sight of the agent. Evaders have a view range advantage Pursuers have a view range advantage Same Capabilities--Capture Same Capabilities--Escape Path Modification Many of the behaviors we create find a path in the roadmap for an agent to follow. The path modification algorithm modifies the output paths from one behavior with respect to the constraints from other behaviors. In particular, this behavior blender combines the path obtained from one behavior (the main behavior) with constraints from other sub-behaviors to create an action for an agent that attempts to satisfy a number of its goals. The combination done will alter or deform the paths the agents are following. Example scenario Agents in group A search the environment for the hiding agents in group B. Once an agent in group A discovers an agent in group B it pursues in order to capture it. At the same time, agents in group A augment their behavior by hiding or being repelled from patrolling agents in group C. Agents in group B that are hiding augment their behavior to pursue or be attracted to agents in group C. The patrolling group C, described earlier, simulates a patrol behavior found in nature where a group of animals will send members on patrols to maintain their territory. Movie1: Example of Three groups using path modification. Movie2: Varying the forces for different behaviors. Related Behavior--Shepherding The shepherding behavior can be viewed as a type of pursuit. The goal of shepherding is for the shepherds to control the motion of a second group of agents. This may involve gathering the other agents to a single location, moving a group of agents from one location to another, or keeping the group of agents out of a certain part of the environment. These other agents may be scattered or close together, and there may be either a single shepherd or multiple shepherds. The shepherds use their presence to attempt to control the desired agents, who will attempt to move away from the shepherds. In the case of multiple shepherds, the shepherds will coordinate their efforts to maintain better control of the second group. More information on the shepherding behavior may be found here. Related Projects Composable Behaviors Group Behaviors using Rule-Based Roadmaps Shepherding Behavior Simulating Group Behaviors Roadmap-Based Group Behaviors: Generation and Evaluation Papers A Framework for Planning Motion in Environments with Moving Obstacles, Sam Rodriguez, Jyh-Ming Lien, Nancy M. Amato, In Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS), pp. 3309-3314, Oct 2007. Also, Technical Report, TR06-010, Parasol Laboratory, Department of Computer Science, Texas A&M University, Sep 2007. Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract) Roadmap-Based Group Behaviors: Generation and Evaluation, Samuel Rodriguez, Robert Salazar, Troy McMahon, Nancy M. Amato, Technical Report, TR07-004, Parasol Laboratory, Department of Computer Science, Texas A&M University, Sep 2007. Technical Report(ps, pdf, abstract) Composable Group Behaviors, Jyh-Ming Lien, Samuel Rodriguez, Xinyu Tang, John Maffei, Arnaud Masciotra, Technical Report, TR05-006, Parasol Laboratory, Department of Computer Science, Texas A&M University, Sep 2005. Technical Report(ps, pdf, abstract) Shepherding Behaviors with Multiple Shepherds, Jyh-Ming Lien, Samuel Rodriguez, Jean-Philippe Malric, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), Apr 2005. Also, Technical Report, TR04-003, Parasol Laboratory, Department of Computer Science, Texas A&M University, Sep 2004. Proceedings(ps, pdf, abstract) Technical Report(ps, pdf) Swarming Behavior Using Probabilistic Roadmap Techniques, O. Burchan Bayazit, Jyh-Ming Lien, Nancy M. Amato, Lecture Notes in Computer Science, 3342/2005:112-125, Jan 2005. Journal(ps, pdf, abstract) Shepherding Behaviors, Jyh-Ming Lien, O. Burchan Bayazit, Ross T. Sowell, Samuel Rodriguez, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 4159-4164, New Orleans, Apr 2004. Also, Technical Report, TR03-006, Parasol Laboratory, Department of Computer Science, Texas A&M University, Nov 2003. Proceedings(ps, pdf, abstract) Technical Report(ps, pdf) Better Shepherding Behaviors Using Improved Shepherd Locomotion, Ross T. Sowell, O. Burchan Bayazit, Jyh-Ming Lien, Nancy M. Amato, Technical Report, TR03-009, Parasol Laboratory, Department of Computer Science, Texas A&M University, Aug 2003. Technical Report(ps, pdf, abstract) Better Group Behaviors in Complex Environments with Global Roadmaps, O. Burchan Bayazit, Jyh-Ming Lien, Nancy M. Amato, In Proc. Int. Conf. on the Sim. and Syn. of Living Sys. (Alife), pp. 362-370, Sydney, Australia, Dec 2002. Proceedings(ps, pdf, abstract) Better Group Behaviors using Rule-Based Roadmaps, O. Burchan Bayazit, Jyh-Ming Lien, Nancy M. Amato, In Proc. Int. Wkshp. on Alg. Found. of Rob. (WAFR), pp. 95-111, Nice, France, Dec 2002. Proceedings(ps, pdf, abstract) Roadmap-Based Flocking for Complex Environments, O. Burchan Bayazit, Jyh-Ming Lien, Nancy M. Amato, In Proc. Pacific Conf. on Computer Graphics and App. (PG), pp. 104-113, Beijing, China, Oct 2002. Also, Technical Report, TR02-003, Parasol Laboratory, Department of Computer Science, Texas A&M University, Apr 2002. Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract) Parasol Home | Research | People | General info | Seminars | Resources   Parasol Lab, 301 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112  Contact Webmaster      Phone 979.458.0722     Fax 979.458.0718  Department of Computer Science and Engineering | Dwight Look College of Engineering | Texas A&M University     Privacy statement: Computer Science and Engineering Engineering TAMU