Project 4: Sheepdog Trials

The Australian border collie sheep-dog is extremely intelligent. It can round up sheep alone, or in combination with other dogs, without direct human control. Your job is to write the code for a sheep dog so that it can effectively and efficiently herd sheep, both alone and in teams.

The trials take place in a large square field of side length 100m, that is partitioned in half by a fence. Precisely in the middle of the fence is a 2m wide gate. A number S of sheep are randomly (uniformly) distributed in one half of the field and the other half is empty. Some number B of the sheep are black, and the remainder are white.

There are two tasks, basic and advanced. The basic task is to move all of the sheep through the gate to the other half of the field. The advanced task is to move only the black sheep, leaving the white sheep in the original half of the field.

Sheep are lazy, and will stay put (grazing) if left alone. However, when a sheep dog comes close, they react by moving in the opposite direction to the closest dog. They have two speeds: walk and run. When a sheep dog is within 10m but further than 2m, the sheep walk at 1m/s directly away from the closest dog. When a dog is within 2m, the sheep run at 10m/s away from the closest dog. Dogs can move at up to 20m/s.

The simulator is discrete rather than continuous, and operates at 0.1s granularity. The new positions of the sheep are calculated based on the positions of the sheep and dogs at the current time. The new positions of the dog(s) are specified by your program, and may be any position up to 2m away from the current position (these dogs can zig and zag!).

Sheep are not very smart about the fencing, which is electrified. A sheep that collides with a fence (either in the middle of the field, or on its perimeter) will bounce off as if it were a ray of light (angle of incidence equals angle of reflection) within a single simulator timestep.

Sheep also have a mild resistance to overcrowding. Sheep that are within one meter of each other on a given turn will move away from each other on the next turn. A direction is chosen by adding unit vectors from each nearby (within 1m) sheep to the current sheep. The sheep will move at 0.5ms in that direction. In the event that a sheep dog is nearby, the two velocity vectors are added to get a net velocity.

Dogs are allowed to climb in among the sheep, so that they can get arbitrarily close to the sheep and to other dogs. Sheep can also climb over/around other sheep if pursued by a dog.

You have d dogs, each of which is executing an instance of the same code, but instantiated with a unique dog-id parameter (between 1 and d). The dogs start in the empty half of the field on the far fence, spread out uniformly. So if the line defining the far fence stretches from (0,0) to (0,100), the d dogs start at $(0,100/(d+1)),(0,200/(d+1)), \ldots, (0,d*100/(d+1))$. Dogs have complete access to all positional information, but do not explicitly communicate with other dogs.

The simulator will detect when the goal is achieved (basic or advanced, depending on the configuration) and you will be ranked based on the time taken to achieve the goal. There will be a timeout to handle cases where the last few pesky sheep simply can't be convinced to go where you want them. In such a case, you will be ranked by the number of sheep transferred (basic goal) or the number of black sheep transferred less the number of white sheep mistakenly transferred (advanced goal).

Some things to think about:

• Should dogs try to handle one sheep at a time (quickly) or many sheep at a time (slowly)? How might the game parameters S, d and B affect this decision?
• Given no explicit communication between dogs, how might you achieve coordinated behavior?

Note that this is a single-player game. Each group will be operating in their own private field.