Home research People General Info Seminars Resources Intranet
| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News

Algorithms & Applications Group
Shepherding Behaviors

Shepherding Behaviors
supported by NSF, Texas Higher Education Coordinating Board
Jyh-Ming Lien, Samuel Rodriguez, Nancy M. Amato
Project Alumni: O. Burchan Bayazit, Ross T. Sowell

Shepherding behaviors are one class of flocking behaviors in which one or more external agents (called shepherds) attempt to control the motion of another group of agents (called the flock) by exerting repulsive forces from shepherds to the flock.


Techniques for a single shepherd
Shepherding behaviors are a type of flocking behavior in which outside agents guide or control members of a flock. Shepherding behaviors can be found in various forms in nature. For example, herding, covering, patrolling and collecting are common types of shepherding behaviors. In this work, we investigate ways to simulate these types of behaviors.

Techniques for multiple shepherds
When the size of the flock gets large or if the flock's behavior makes it difficult to influence, a single shepherd cannot adequately control the flock. In this work, we study how a group of shepherds can work cooperatively without communication to efficiently control the flock.


Techniques for a single shepherd
Shepherding Herding.
Shepherds steer a flock from a start region to a goal region. Study of the herding behavior is used to construct robots as a cheaper alternative to sheep dogs and may be used to study neuron migration process in which a repulsive molecule pushes young cells to their permanent position in a brain.
Herding Movies.

Shepherding Covering.
Shepherds guide a flock to visit the entire environment. Study of the covering behavior provides a new paradigm to accomplish tasks like mine sweeping and surveillance.
Covering Movies.

Shepherding Patrolling.
shepherds protect a designated region from the flock entering it. Study of the patrolling behavior may be used to build robots to prevent wild birds from being sucked into airplane engine in airports and to keep swimmers or children away from dangerous zones on a beach or in a school.
Patrolling Movies.
Shepherding Collecting.
shepherds gather scattered flock members into a designated region Study of the collecting behavior may be used to construct robots that gather and skim off spilt oil from oil tankers on the sea to avoid further damage to our ecosystem (in this case, skimmers are shepherds and floating oil will be the flock) and may be used to study how predators hunt.
Collecting Movies.


Shepherd's Locomotion

We define a shepherd's locomotion as the manner in which the shepherd will move in order to control the movement of a flock. The shepherds locomotion remains invariant in different shepherding behaviors and dramatically affects the quality of simulation. We divide the shepherd's locomotion into two sub-problems: approaching and steering.


Approaching
In the approaching problem, we study how the shepherd goes to the steering point near the flock from its current position.

Approaching the flock using a straight line using a circular safe zone using a dynamic roadmap

Steering
In the steering problem, we study how the shepherd steers the flock toward the milestone.

steering the flock straight behind side-to-side behind no turn steering stop-turn steering pre-turn steering

A border collie walk side to side behind the flock in order to steer the flock.

Movies

Herding 1

  • Straight-line approaching and steering. (divx 3.7 MB, mpeg 5.1 MB)
  • Safe-zone approaching and side-to-side and turn steering. (divx 1.7 MB, mpeg 3.2 MB)
  • Dynamic-roadmap approaching and side-to-side and turn steering. (divx 1 MB, mpeg 1.8 MB)
  • Herding 2

  • Straight-line approaching and steering. (divx 4 MB, mpeg 5.7 MB)
  • Safe-zone approaching and side-to-side and turn steering. (divx 5.3 MB, mpeg 8 MB)
  • Dynamic-roadmap approaching and side-to-side and turn steering. (divx 4.7 MB, mpeg 7.2 MB)
  • Covering

  • Dynamic-roadmap approaching and side-to-side and turn steering. (mpeg 56 MB)
  • Patrolling

  • 5 flock members (using straight-line approaching and steering). (divx 10.5 MB, mpeg 15.4 MB)
  • 10 flock members (using straight-line approaching and steering). (divx 10.5 MB, mpeg 15.4 MB)
  • 20 flock members (using dynamic-roadmap and side-to-side and turn locomotion). (divx 10.5 MB, mpeg 15.4 MB)
  • 40 flock members (using dynamic-roadmap and side-to-side and turn locomotion). (divx 10.5 MB, mpeg 15.4 MB)
  • Collecting

  • Sheep Flock (using dynamic-roadmap and side-to-side and turn locomotion). (divx 10 MB, mpeg 15 MB)
  • Duck Flock (using dynamic-roadmap and side-to-side and turn locomotion). (divx 8.2 MB, mpeg 12 MB)


  • Techniques for multiple shepherds
    In this work, we extend the idea of shepherding with a single shepherd to using multiple shepherds for large or difficult to manage flocks. More specifically we study how a group of shepherdscan work cooperatively and without communication to efficiently control the flock. In agriculture, it is common to see mutliple shepherd dogs herding a flock.


    Shepherd Formation
    Two formations that we tried for shepherds to push a flock were a straight line behind the flock and an arc behind the flock. Though both formations do a good job of evenly distributing the force evenly among the flock, the arc formation concentrates the forces toward the center of the flock.

    (a) a straight-line formation (b) an arc behind the flock



    Steering
    While steering the flock, the shepherds could take on a straight-line or side-to-side motion, behind the flock depending on how many other shepherds were also assigned to a flock group. The side-to-side motion works well for a single shepherd working on a group but when working with other shepherds, the shepherds use only the striaght-line steering.

    (a) Steering using side-to-side motion (b) Steering using straight-line behind the flock


    Matching Shepherds with Steering Points
    Once the shepherd has determined the possible (formation of) steering points, it needs to choose which steering point it will use. These steering points must be chosen by each shepherd independently, i.e., without communication between shepherds. We show three possible methods for choosing a steering point Vector Projection, Greedy Distance Minimization and Global Distance Minimization.

    (a) vector projection (b) greedy minimization (b) optimal

    Movies

    Video
  • The idea is that many of these simple behaviors can all be combined depending on the state of flock to create interesting and complex behaviors.
    (divx 26 MB, mpeg 28 MB)

  • Papers

    Related Projects

    Roadmap-based Techniques
    Evacuation Planning
    Pursuit-Evasion in Realistic Environments
    Planning Among Moving Objects


    Papers

    Roadmap-Based Techniques for Modeling Group Behaviors in Multi-Agent Systems, Samuel Rodriguez, Ph.D. Thesis, Department of Computer Science and Engineering, Texas A&M University, Jan 2012.
    Ph.D. Thesis(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, abstract)