(Solved): 1 Your First Rodeo Figure 1: A square corral containing a bull (B), a robotic rodeo bullfighter (C), ...

1 Your First Rodeo Figure 1: A square corral containing a bull (B), a robotic rodeo bullfighter (C), and a target (

). A bull is running loose in the above square corral. The robotic rodeo bullfighter is meant to pen the bull, by getting it to chase them, and leading it to the square

so that it can be closed in

. The rules are these: The bull can only move up/down/left/right (limited by the walls/obstacles). The robot can move in any of the eight immediate neighboring directions (limited by the walls/obstacles). Each round, the robot moves, then the bull moves. If the robot is outside the

square surrounding the bull, the bull moves uniformly at random in its available directions. If the robot is within the

square surrounding the bull, the bull will charge with equal probability in any direction that doesn't take it farther (manhattan distance) from the robot. The bull cannot enter the same square as the robot, and vice versa. The bull will skip moving if it has to. (Shy bull.) The game is over when the bull walks onto the

. Answer the following questions with math, code, or computation: Intuitively, if the robot moves strategically, argue that the game can't last forever (with probability 1). (2 points) How many possible states can the game be in? (

points) Let

be the minimal number of rounds remaining expected to corral the bull on the

when the robot is at position pos

and the bull is at position pos

. Express

of a given pair of positions in terms of

of the feasible 'next' positions. What are the cases to consider? Are there any positions that you know the value of

for? (30 points) Describe an algorithm for computing

. (

points) Implement that algorithm, and compute

for the pictured configuration. Can the robot pen the bull in finite (expected) time? If so, what is the expected time? (

points) (Bonus) The rules are the same, but now the bull wants to kill the robot, and will move into the robot's cell and crush it if it can. The robot wants to survive and pen the bull. If everyone moves optimally, who (if anyone) wins? (

points) (Bonus) What would a good heuristic estimate for

be, as a function of

and

. Why is this useful, practically? (10 points)

This assignment has been created by Dr. Charles Wes Cowan, Rutgers University.