Roadmap-Based Group Behaviors: Generation and Evaluation

Algorithms & Applications Group
Roadmap-Based Group Behaviors: Generation and Evaluation

Roadmap-Based Group Behaviors: Generation and Evaluation
supported by NSF
Sam Rodriguez, Robert Salazar, Troy McMahon, Nancy M. Amato

We explore the benefits of integrating roadmap-based path planning methods with agents performing group behaviors to achieve different objectives. We show how a wide range of group behaviors can be facilitated by using dynamic roadmaps.

Simulating the coordinated behavior of multiple agents has been studied in many fields including robotics, computer animation and games. Creating complex behaviors for a group of agents in order to achieve some behavior can be a difficult and time consuming task. Automated approaches for motion generation typically involve explicitly defining a set of possible agent behaviors, associating appropriate behaviors with all environmental events, and setting the priorities among various behaviors in every possible situation.

Generally, such approaches are pre-tuned to particular situations and are difficult to adapt for other scenarios or for different sets of behaviors. An adaptive approach to automatic behavior generation will typically involve the steps of creating initial behaviors, selecting potential behaviors to use, and adaptively selecting between an approapriate behavior depending on the performance of a given behavior.

We focus on two aspects of the adaptive approach to behavior generation. First, we propose a variety of seaching and hiding group behaviors. The behaviors we propose use an underlying roadmap which will be described more later. Although not all of these behaviors can be considered the most effective, there can be applications where each behavior can be useful. In addition, in a complete framework, the searching and hiding behaviors could be combined adaptively with their respective variants to produce more effective searching and hiding behaviors. Even though we focus on searching and hiding behaviors, the type of analysis we propose here is general enough to work for many kinds of behaviors.

Secondly, we focus on how these behaviors can be evaluated. The evaluation of a behavior that a group of agents are executing can depend on the objective the agents are trying to achieve. For example, the evaluation of agents searching through an environment would differ than that of agents trying to spread out through the environment to occupy the most space depending of the evaluation function. The coverage of agents searching through an environment can be seen in Figure 1. The evaluation can also depend on the type of behavior being evaluated (i.e., a behavior that can be evaluated on its own versus one that needs to be evaluated while considering another group of agents).

Covering Behaviors

Basic

Roadmap based

Goal is to visit as many nodes and edges in the roadmap

As agents traverse roadmap, adjust edge weights

Select paths in the roadmap biased to uncovered areas

Movie(mpg): Covering

Scanning

Agents use roadmap for finding paths in the environment

Step1: Generate points that are unobservable to the agent’s current location

Step2: Agents attempt to make scan points visible by moving toward unobserved locations

Communication makes this behavior more effective

Movie(mpg): Scanning

Rendezvous

Agents use roadmap for finding paths in the environment
Step1: In groups, a goal location is generated

Step2: Paths are found using the roadmap

Step3: The roadmap is adapted as paths are extracted to bias the next paths extracted to unexplored areas

Movie(mpg): Group Rendezvous

Territorial

Agents try to claim a set of nodes in the roadmap

Nodes claimed represent their territory

Claimed nodes eventually become unclaimed

Agents traverse the roadmap to maximize the number of nodes claimed

Movie(mpg): Territorial

Hiding Behaviors

Basic Hiding

An agent will remain at a hiding location until it is discovered

When discovered, the agent will then determine the next hiding location

A more advanced behavior will select paths to the new hiding location based on how “hidden” a path is

Movie(mpg): Hiding

Zone Avoid

An agent will keep more information about agents seen in the environment

Agents will store the last observed locations of opposing agents

The agent will attempt to approximate the locations that observed opposing agent can be in

Communication can be used to pass along opposing agent information to other agents

Movie(mpg): Zone Avoid

We show the evaluation of the Basic Covering behavior varying the number of agents from 5 to 150 agents. A movie and results are shown below.

Movie (mpg)	Plot

For more information and results, please see the paper on generation and evaluation of behaviors below.

Related Projects

Group Behaviors using Rule-Based Roadmaps
Planning Motion Among Moving Obstacles
Shepherding Behaviors
Composable Group Behaviors

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)

Department of Computer Science | Dwight Look College of Engineering | Texas A&M University
Privacy statement: Computer Science Engineering TAMU