Using sheep because cats won’t herd

Before we can implement AI/ML, it helps to understand the theory. This enables us to think about what might be useful. Of course please feel free to throw random ideas and see if any work. I am not a fan of that and don’t think it’s effective, but maybe your experience will differ.

The herding principle I am going to describe works for 1 or 25+ sheep. I would say thinking about how a lone sheep behaves helped.

I am intentionally limiting to controlling a flock and not fetching stragglers.

• Developing a strategy to get stragglers is not beyond the scope of mere mortals…

• You’d need to pick the furthest ones and steer them to the mass. 

• Any workable approach needs to avoid further fragmenting of the herd – best achieved by moving the herd somewhere away from the stragglers and then fetching them one by one.

• Knowing which straggler to target (order of) requires additional logic.

• Knowing how to avoid fragmenting requires a separate logic.

I like a challenge, but the above is going to use a lot more cunning and effort to achieve. Kudos to anyone smart enough to achieve it!

Herding reliably is far trickier than meets the eye!

Step 1. It’s about anticipating how the sheep will respond to any given position of a dog

Maybe I should define some annotations used in the diagrams:

Notice that I intentionally use “theory”. That’s because whilst it’s the expected outcome, it is not a precise/consistent behaviour.

Step 2. Knowing how to steer, it becomes computing the deflection required to ensure the sheep follow the desired path

Notice how the dog has to pick a very different path, requiring it to position itself carefully to make the sheep follow the dots?

Step 3. Testing the theory for single sheep

The reality with 1 sheep is that everything behaves as expected. Or at least with my “sheep” modelling. The sheep move along the line that intersects with the centre of mass.

Regardless of distance (as long as the dog is close enough to threaten the sheep), the sheep move in the direction expected. These were drawn using some “test” suite code. I cannot emphasise enough how important it is to accurately know the behaviour, in this instance, it’s simple to set up a sheep + dog and saves images showing what happened.

Step 4. Testing the theory for a flock of sheep

Hmm, “practice” please meet “theory”. You hopefully now are getting some idea of the pain solving this using AI will be. The cute fluffy thing didn’t read the theory manual and have no intention of making our job easy. Honesty should be my middle name, and I will mention complacency got the better of me. I skipped this step; I wrote the theory after struggling with practice! Don’t be like Dave, be smart.

At a rudimentary level, it’s a linear relationship, moving the dog so the angle sheep are travelling deflects sufficiently

Here’s my attempt to explain behaviour, moving the dog (grey blob, no expenses spared on graphics, sorry) to the black blob position to steer the sheep (towards yellow blob). It’s worth remembering although dogs jump, not sideways this radically. As the dog moves to the new position, the sheep are not obligated to wait until the dog is ready. This has a huge impact on behaviour.

Simple mathematics can calculate:

1) Angle the flock is heading

2) Angle the flock need to head

(2)-(1) = deviation required (angle wise)

The hard part is knowing where to place the dog. For this, we need to remember the line of action is acting through the centre of mass which we refer to as CoM.

3) Math.Atan2() for the position of CoM vs. the position of the dog provides us with the required angle of action.

In theory, the angle of adjustment required is a subtraction of (3) from (2)-(1).

That leaves us with the small complication of “speed” / “distance” of dog from sheep…

Deviation vs. Distance

Using simulation, we test the dog (yellow blob) driving the flock in a straight line.

Notice the orange line is the INTENDED path. At various distances, the deviation can be wild. At 150px, it is below the intended path, and at 50px above the intended path. Seeing this makes me think the sheep hate me.

The results seem inconsistent; the deviation varies at different points 14 frames in, the deviation @100 is like below, yet on the line at 19 frames (above).

How much deviation occurs is a function of the way the sheep apply coherence, alignment and separation with respect to their random starting positions. Think of multiple variables. Also, think of random herds.

Moving the dog

The previous visuals show where the dog STARTS at the distance and remains so, we have to know what happens if the dog moves forward too… Here we have frame by frame.

Pesky virtual sheep don’t always behave when herding. This is not an atypical example. Why? The sheep drift as a cohesive group, following an average path, that might not be the direction the dog is pushing.

Early on, it’s moving off the desired path; that error accumulates for each frame. 20 frames on, it’s out by 20 degrees or so.

That means any AI has to take constant corrective action before the deviation is impossible to correct.

Or another way to look at the same thing, but this time simplifying..

The dog didn’t like linear algebra, trigonometry, geometry and other mathematical calculations. There is another way to coax them, that lays the foundation for human teaching.

x0, y0 describe the dog relative to the flock

x1, y1 describe where the dog needs to go relative to the flock

How we calculate x1,y1 is somewhat a moot point. The dog doesn’t care, they just need to know where we want them to go. This looks like a job for backpropagation.

And it has the potential to learn: i.e. human does it, the app records x0,y0,x1,y1 and desired angle

If *that* works, then we can remove the calculated training and use “human data” to seed the training data.

The dog then spends time repeatedly going over what it was taught (we’ll not going to tell the dog that we are backpropagating to avoid upsetting it).

Maybe you don’t like mathematics? I don’t blame you.

Finding the best data to train the AI isn’t always easy. The big bucks question you should ask is whether the mathematical understanding works. I’m glad you ask!

OK, it wasn’t perfect, but you get the idea. Did I label it “heuristics”? Yes. This isn’t AI, be patient, we’ll get to that.

The yellow blob is where we need to position the dog (a visible black blob means the dog isn’t where it should be). The long line thru the flock and desired dog position indicates where we want the sheep to go. We’re targeting the grey blobs (waypoints). Given I am not going to whistle at your dog or mine and shout instructions we need to find a way to tell the dog what we require. It uses waypoints.

Beginning to believe me? Also, are you feeling this herding is harder than you originally thought? I hope so!

The code is really short:-

/// <summary>
/// Apply heuristics to work out what angle to move the dog, and how quickly.
/// </summary>
/// <param name="inputToAI"></param>
private void SetDesiredPositionByUsingHeuristicsToSteerTheDog(List<double> inputToAI)
{
  /*
   *     + backwardsPointForLine
   *      \
   *       \
   *        \  
   *         x closestPointOnLine
   *    o     \
   *   dog     \
   *            \ 
   *             + desiredPointAtTheEdgeOfSheepCircle  
   *              \o
   *   sheep ->  o x o________  
   *               o.     |
   *                 .   /  2*PI-AngleToNextWayPointInRadians()
   *                  .--
   *                   .
   *                    .
   *                     O 
   *                   waypoint
   */

  PointF centreOfMass = flockBeingHerded.TrueCentreOfMass();

  float arc = (int)Config.DogSensorOfSheepVisionDepthOfVisionInPixels;

  double desiredAngleInRadians = inputToAI[2] * Math.PI - Math.PI; // [2] is scaled with "/ Math.PI" to make -1..1, so we reverse that. We then need to rotate 90 degrees

  float cosDesiredAngle = (float)Math.Cos(desiredAngleInRadians);
  float sinDesiredAngle = (float)Math.Sin(desiredAngleInRadians);

  float radius = ClosestDogMayIntentionallyGetToSheepMass();
  PointF desiredPointAtTheEdgeOfSheepCircle = new((float)(centreOfMass.X + cosDesiredAngle * radius),
                          (float)(centreOfMass.Y + sinDesiredAngle * radius));

  // away from destination thru CoM
  PointF backwardsPointForLine = new((int)(centreOfMass.X + cosDesiredAngle * arc),
                     (int)(centreOfMass.Y + sinDesiredAngle * arc));

  // closest is the point on the line (from opposite side of CoM) to the dog
  // i.e. closest of desired point on the line between CoM and backwards point
  MathUtils.IsOnLine(centreOfMass, backwardsPointForLine, desiredPointAtTheEdgeOfSheepCircle, out PointF closestPointOnLine);

  DesiredPosition = closestPointOnLine;
}

/// <summary>
/// Number of pixels dog must attempt to keep away from sheep centre of mass.
/// </summary>
/// <param name="pherd"></param>
/// <returns></returns>
internal static float ClosestDogMayIntentionallyGetToSheepMass()
{
  // hard-code, because if we compute based on all the sheep, stragglers kill the algorithm
  return 55;
}

We’ve proved that the “rough” theory is correct, we now need to move on to ML/AI.

We do exactly that on page 3.