Project 4: Exercise the Dogs

You take your dogs to the dog park, and have a bag of tennis balls that you use to exercise them. Each of your d dogs has its own tennis ball that it recognizes, and it ignores all other tennis balls. When you throw a ball, the corresponding dog immediately chases it until it reaches the point where the ball landed. During the chase, it gets exercise. On the way back, however, the dog walks and does not get exercise. Exercise is measured in seconds, and accumulates only when the dog is running. Each of your dogs may have a different speed.

The dog park hosts many dogs/owners who use the park at the same time, all hoping to exercise their dogs. Over time, the owners have collectively trained their dogs to observe the following behavior. When a dog (say Fido) picks up a tennis ball, it checks to see if its owner is within 10 meters. If so, Fido returns to its owner. If not, and there is a person (say Mary) who is within 10 meters and closer to Fido than all other owners, the dog walks over to Mary, stopping 1 meter from her. Fido then waits up to 30 seconds for Mary to take Fido's tennis ball from him and throw it. If Mary throws Fido's ball, Fido chases it and the process continues. If after 30 seconds Mary does not take Fido's ball, or if Mary changes position within the 30 seconds without taking Fido's ball, Fido will abandon Mary and walk back to its owner. Fido will wait indefinitely for its owner at a 1m distance.

Each dog breed has its own running speed given below, and its walking speed is one quarter of its running speed:

Labrador	10m/s
Poodle	8m/s
Spaniel	7m/s
Terrier	4m/s

We'll simplify things by ignoring speed-up and slow-down phases of movement, and just assume that the dogs instantaneously start and stop running at their full speed, in a straight line towards their destination. When dogs are walking, it doesn't matter how close they get to other dogs or people -- we'll assume that they can squeeze past. However, if a dog is running and comes within 1m of a person or another dog, they immediately slow down to a walk until the obstacle has passed. (When walking, they don't get exercise.)

The simulation will happen at a fine granularity (e.g., 0.01 seconds per step) in order to properly handle collision detection for the faster dogs. You will probably want to visualize the simulation at a coarser granularity most of the time, e.g., one frame every simulated second. Every player will be assigned a name by the simulator from the set { Alice, Bob, Carol, Dave, ... }. See the simulator for a complete list. If your code is being used for two instances of an owner, each instance will be assigned a different name.

Owners can do one of the following things every 5 seconds:

1. Throw a ball. You have a throwing device that lets you throw the ball up to 40m in any direction. We'll assume the ball travels faster than the fastest dog, and lands without rolling. If you try to throw the ball outside the park boundary, the simulator will prevent the throw from happening. Retrieving the ball from a returned dog happens within the same 5 second window as throwing the ball.
2. Move to a new position that is up to 5m away from the current position. Any returning dogs will dynamically adjust their direction to your position at any point in time. Returned dogs will follow you to maintain the 1m separation.
3. Call out a signal to other owners. You can use any single English language word of up to 10 letters, or any one of the owner names. Owners within 50m of you will hear your message. You also get notified (on the next 5-second action step) each time you hear another owner call out a message.

When you throw the ball, you specify the coordinates of the point you are aiming for. While you are relatively accurate, you do not have pinpoint accuracy. The ball will land somewhere within a disc of radius 1m centered on your target point. The simulator will choose an offset and direction at random such that all points in the disc are equally likely.

Note that the 30 second wait time for a non-owned dog starts when the dog arrives, meaning that you will probably have up to 5 turns with an opportunity to interact with that dog.

The dog park is 200m by 200m, and n owners all show up at the gate at one of the corners at opening time. Each owner has exactly d dogs, but may have a different mix of the four dog breeds. (The set of mixes is a configuration parameter.) You have two potentially compatible goals:

1. Minimize the time T taken for all your dogs to have achieved 30 minutes of exercise. (Note that you can continue to stay in the park after your dogs have completed their 30 minutes if you wish.)
2. Minimize the average time A taken by all the other dog owners to have achieved 30 minutes of exercise for their dogs. Since this is a community of dog owners who know each other well, you like to help each other out.

Your final score is therefore computed as (T+A)/2. This scoring function rewards cooperation. The game mechanics also enable cooperation. For example two owners could throw balls back and forward for a dog so that the dog gets exercise traveling in both directions. The challenge will be to self-organize into configurations that are efficient at exercising the dogs.

We'll provide a dictionary of (nonoffensive) English words that you can use for signaling -- the simulator will check whether your word is in the dictionary or is a player name. In principle you can formulate sentences, but each word takes 5 seconds to communicate, and you can't do anything else while you're talking. On the other hand, you can listen while doing other tasks, and are notified of each spoken word at the end of the 5 second interval of the speaker, in time to use that information for your action in the next 5-second step. Your hearing is so good that you can make out individual words even if they're spoken at the same time.

Your player can see the positions of all owners and all dogs at the end of each 5 second interval, but as mentioned previously, can only communicate with other owners who are within 50m. You can also see whether (at the given moment) each dog (a) has a ball, (b) is running, (c) whether it is heading for its ball or a person, including the identity of the person, and (d) if it is waiting for a person to respond, and if so, how long it has been waiting. The simulator will keep track of the amount of exercise each dog accumulates. You can access this information from the simulator for your dogs, but not for other owners' dogs. The simulator will enumerate your dogs and your tennis balls, so that dog number 1 chases ball number 1, etc. The breed of each dog is accessible via the simulator. The balls and dogs will also have an owner (a name from the name list) that will enable you to specify actions specific to both your dogs/balls and dogs/balls belonging to other owners. At the start of the simulation, all dogs will be carrying their respective tennis balls.