Lab11 - Game Theory in Robotics

A problem in computer science where a set of pursuers is trying to catch a set of evaders.

In greedy policy the next-best state is selected in each discrete step of the game simulation without considering longer prediction horizon.
Usual policies incorporate distances between individual agents as follows:

• For evaders select the most distant node to the closest pursuer
• For pursuers select the closest node to the closest evader

Find counterexamples where greedy policy will fail.

• Based on euclidean distance
• Based on shortest paths distance

• MCTS (https://en.wikipedia.org/wiki/Monte_Carlo_tree_search)
  • Implementation by tree vs. hash map
• UCB1
• Dealing with simultaneous moves (http://storage.kghost.de/cig_proc/full/paper_61.pdf)
  • serialized UCT
  • decoupled UCT (need for randomization)
• MCTS improvements (RAVE)