        |
 |
|
|||
|
|
Naturally-Inspired Exploring, Pursuit and Evasion Behaviors
supported by NSF
Sam Rodriguez,
Robert Salazar,
Roozbeh Daneshvar,
Philip Coleman,
Nancy M. Amato
|
Group behaviors are an inherent part of the world we live in. They arise in many
scenarios ranging from search and rescue operations, to hunting, to even soccer.
Our research explores the degree to which a common framework can be used as the
basis for simulating group behaviors for a variety of agents, ranging from animals,
to humans, to artificial agents such as robots. In particular, we focused on developing
behaviors inspired from nature and exploring their relation to robotics-based
multi-agent systems. We use natural behaviors as the basis for developing more
complex agent-based systems because they constitute a rich set of effective
behaviors that have evolved over time. Through this evolution these behaviors
have been optimized for a complex and dynamic environment, namely our world.
Using our system we have generated various types of behaviors ranging from simple covering strategies to more complex group pursuit behaviors. These behaviors include new approaches to the standard exploration or pursuit problem and have been inspired from behaviors seen in animals such as chimpanzees, wolves, and lions. We split the behaviors into three categories; exploration, evasion, and pursuit. For the exploration behvaviors we created three different variations. These included; exploration using scanning, exploration using rendezvous points, and patrolling. For evasion, we present models for flee-and-freeze and flee-and-hide behaviors. Finally for pursuit, we created a basic pursuit behavior and a surround and capture behavior. The results from these behaviors help show that by looking towards nature for inspiration we can create interesting new strategies that can provide a basis for artificial multi-agent systems. |
|
Image Links Wolves attack Bear, Gnus crossing river, Lions and Zebras, Wolves and Bison (1), Wolves and Bison (2), ants
Exploring the environment is a common and useful behavior that includes activities such as vacuuming, foraging for food or resources, locating prey, or finding suitable places for relocation. We use the General Exploration Algorithm to model all such exploring behaviors.
The general exploration behavior is specialized by selecting how the agents choose the areas to explore and how they will explore them. The behaviors can also include cooperation to manage explorations in groups.
We provide several exploration strategies, including basic exploration, scanning, rendezvous and patrolling.
Basic Exploration
|
The basic exploration behavior attempts to maximize coverage, and utilizes indirect communication where agents mark the environment, similar to pheromones used by ants. The basic exploration behavior attempts to cover as much of the environment as possible (much like an animal foraging for food by searching every plant). In this behavior, the agents utilize the edge weights in their roadmap to determine their next destination. As they traverse the environment, they mark their path so that other agents will be less likely to explore the same area. |
ants
|
|
The scanning behavior biases exploration towards areas that are outside an agent's vision (not scanned) and is reminiscent of behavior seen in monkeys. The scanning behavior explores the environment based on locations that it cannot currently observe. To do this, the agents generate a list of points in the environment that are currently unobservable, whether due to the distance or being obstructed from view by an obstacle. The agents will remove points from the list as they are seen, either by the agent or a neighboring agent in the group. The agent will choose the next point to actively seek by selecting the point that is nearest to it. In an open environment, this will result in the agent performing a series of loops that are centered near the location of the last point visited from the previous list. Furthermore, since the points are random, the direction that the agent will go towards the first point is also random. Furthermore, another strategy used is to leave a resource in a different direction than when entering, which is similar to the random direction of the first point in a newly generated list. When the points are set to be generated throughout the environment, it is similar to monkeys using their memory of where they have been recently. |
|
The rendezvous behavior is a group-based strategy where the agents in a group select a common subgoal (rendezvous point) but try to maximize coverage by taking different paths to the rendezvous point. The tactic of the Rendezvous behavior is to split up so as to search a wider area on the way to a point of interest. In particular, the Rendezvous behavior attempts to increase the area explored by a group of agents as they travel to a goal. The first step is to select a goal. This goal will determine the area to be explored, as several different routes between the goal and the current location will be traversed. The agents are divided into subgroups, with each subgroup searching for its own goal. The agents use a temporary re weighting of the roadmap to bias other agents in the subgroup away from taken paths, while not affecting paths to subsequent goals. To do this, the agents sequentially find paths along the roadmap, and modify the edge weights of the roadmap as they find paths. Subsequent agents attempting to find a path will be biased away from the re weighted edges. The changes in weights are temporary, so that paths to subsequent goals will not be affected. Furthermore, it is possible to re-weight edges that are near to the path, so that the agents are also biased away from paths that are close to paths that are already taken but merely go through different nodes on the roadmap. |
|
Unlike the behaviors whose goal is to maximize coverage, patrolling typically concentrates on areas near a boundary, and many times is done periodically in groups. For example, chimpanzees select either the border of their territory or the area near their main living area and wolves tend to select borders of their realm. The behavior while patrolling can also vary, e.g., robotic agents may make maneuvers to improve sensing, police officers may slow down in areas of interest, chimpanzees make frequent stops during patrolling and remain quiet unless they encounter neighbors and wolves scent-mark territorially on a patrol. The patrolling algorithm follows the general exploration algorithm. The first step is to determine which regions of the environment will be patrolled and which agents will do it. It may be that all agents patrol the entire territory, or, the agents might form groups to patrol portions of the territory. Next, a patrol route is determined, including setting parameters such as how closely the patrol route follows the boundary of the patrol area, how closely the patrollers must follow the patrol path, and how frequently sites on the the patrol route should be visited. This route takes into account the patrol areas that have yet to be patrolled. Then, the agents patrol the identified route. This process will be influenced by the degree of coordination in the patrol group and the parameters set in the previous step. Finally, periodically throughout this process, the status of the patrollers is evaluated and it is determined if adaptation is needed or if the patrol is complete.
|
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 is similar to that used by the red colobus monkeys in the Tai National Park. The monkeys freeze in their location when they are being hunted, and when the hunter makes a move toward them they tend to flee farther away and then freeze 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.
|
The strategy that the hiding behavior uses to attempt to evade pursuit is similar to that used by the red colobus monkeys in the Tai National Park. The monkeys will freeze in their location when they are being hunted, and if the hunter makes a movement towards them, they tend to flee farther away and then freeze again. This behavior is similar in that the agents will remain in their current location, and once they know they have been detected, they will flee to what they believe is a safer location, where they will again wait. 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 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 agents will need to evaluate the necessity for evasive action as they move along their path. This behavior also has the capability to use memory and communication to enhance the ability to avoid pursuers. |
|
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. |
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. When using communication, the basic pursuit is similar to hunting in wild dogs, which will chase a single target as a pack, and often makes its captures on faster prey when one or more of the dogs takes a shorter route than the prey. The surround and attack behavior requires a higher degree of cooperation from the pursuing agents. It is inspired by the positioning strategies observed in lions and dolphins when preparing to attack their prey. The predators 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.
|
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. |
|
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. |
For more information on the behaviors and results, please see the paper on
naturally inspired group behaviors below.
Related Projects
Group Behaviors using Rule-Based Roadmaps
Roadmap-Based Group Behaviors: Generation and Evaluation
Planning Motion Among Moving Obstacles
Shepherding Behaviors
Composable Group Behaviors
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 |
