RPG Math - Problem 9

Recently, I have been talking to some professors in order to get advice on what classes I should take during the next few semesters so I can fill out my Program of Study Form, where I will create a plan for what courses I will take during my time at UIUC. One professor I talked to is Steven LaValle, a robotics researcher who specializes in motion-planning and navigation algorithms for robots. Some of the problems discussed in his book include things like, given a map of an environment and limited sensing ability, what's the best way for the robot to move in order to get enough data to find out where it is in that environment?

Recently, when I was visiting the Amtgard group in Peoria, the first part of the quest involved a motion strategy problem very similar to these. The scenario was as follows:

- The battlefield was approximately a rectangular field. At one corner was the "destination."
- At the beginning of the game, all the 'questers' (about 6-8 of them) were blindfolded, disoriented, and placed at an unknown location on the battlefield.
- The goal of the questers was to get to the destination. If a player ran into the edge of the battlefield, he would be directed back in by a reeve, no penalty suffered. However there were also "kill zones" in the battlefield that contained enemies. If a player moved into (or too close to) one of the "kill zones" then the enemies would kill them. (The player would then come back to life a few minutes later where he was, and would have to move away from the kill zone before continuing.)
- Although questers were blindfolded, they could still hear what was going on, which meant they can hear if someone is getting killed and would then know approximately in what direction that kill zone was.

Although I had actually read some of LaValle's book, I didn't remember enough of the part about motion planning under incomplete information, so that didn't really help me much - I got hit a total of three times (although I only died once - it took two hits to kill me, and I got healed when I got to the destination.) But that did give me an idea for another RPG Math problem. this is a much more simplified version of what happened in the game, but it should still be interesting and give me a chance to talk about some more algorithm techniques. With that out of the way, we now present...

Problem 9: The Killing Fields

Consider a square battlefield X units on a side. The battlefield contains a total of N "kill zones", the location of which is unknown, and each of which is a circle of radius at most 1. (Kill zones may extend off the side edges of the battlefield, but may not cross or overlap the top or bottom.) The goal of the "attacker" is to go from the bottom edge of the battlefield to the top edge of the battlefield. The attacker can start at any point on the bottom edge and move in whatever path he wants to get to the top. If the attacker hits a "kill zone", he is dead, and has to go back to the beginning and choose a new path, and he knows exactly where he was when he was hit. The goal of the attacker is to minimize the number of deaths before he is able to get to the top.

9a. Prove that no matter what method the attacker uses to choose his paths, there is an arrangement of "kill zones" such that he will take at least N deaths. (Hint: Imagine that you were the defender and you knew the attacker's strategy. How would you place the kill zones?)

9b. Suppose that N < (X/4). Show that the attacker has a strategy such that he will never take more than N deaths.

9c. Suppose that N > (X/2). Suppose that the attacker uses the strategy that minimizes the "worst case" number of deaths that he will suffer. What is the maximum number of deahts that he can guarantee he will not suffer more than, in terms of N and X?

The solution is here.