Ultimate Game of Hide-and-Seek

March 2, 2017

Nick Meyer, PhD Candidate

All of us remember quietly creeping around our homes in our childhood years searching for a friend who was likely hiding in a closet somewhere. The friend was supposed to remain in the same spot, but we all know they secretly moved after they heard us search a nearby room. To find our friend, some of us randomly checked certain parts of each room and, consequently, overlooked a nook here and there. Others, perhaps unknowingly, searched the rooms in an organized and strategic fashion, and they likely found their elusive friend more easily. It turns out that we weren’t just goofing around like our parents said, but we were actually preparing for possible careers later in life. Hide-and-seek applies to many real-world problems. Perhaps a high-ranking government official is tasked with tracking down an adversary who is carrying nuclear material. Or maybe law enforcement is responding to the scene of a crime and the suspect has fled. Whatever the situation might be, experts in the field typically use empirically proven strategies and knowledge of the scenario to inform their search patterns. We hope to develop analytical tools to complement expert knowledge and inform decisions in unknown hide-and-seek scenarios.

This project was motivated by my experience as a summer intern at a national laboratory. My mentor had worked on projects involving patrolling borders and scanning incoming/outgoing vehicles, and most of my research involves sequential decision problems. Hide-and-seek lies somewhere in the intersection. We frame the problem as a group of search agents pursuing a single, evasive adversary. The units move in discrete time and discrete space. Currently, agents lie on a square in a grid. Actions for each agent are to move forward, backward left, or right. When pursuing an adversary, critical information can be provided by a third party. In our simulations, an informant will appear at random time points and provide a location for the evader. This information may or may not be reliable, and thus we must determine the credibility of the informant. Our goal is to combine history information from the search agents with information from the informants to estimate the strategy that minimizes time-to-capture. Experts will be able to utilize this methodology to inform real-time decisions in the field.

To demonstrate the work, we are developing an interactive viewer using Lego robots. One of the robots will be the adversary while the rest are the search agents. A human will be able to control the adversary from a tablet in a separate room where they cannot see the pursuers. They will tell the evader where to move and see how long they can survive without getting caught. We are very excited about this work and hope the interactive demonstration will facilitate others’ understanding of the methodology.

Lego robots

Nick is a PhD Candidate whose research focuses on reinforcement learning, machine learning, and robotics. We thought this posting was a great excuse to get to know a little more about him so we we asked him a few questions!

  • What do you find most interesting/compelling about your research?

    The vast areas of application for the research is what I find most interesting. Seeing practical applications for the research reminds me of the importance and provides motivation.

  • What do you see are the biggest or most pressing challenges in your research area?

    Figuring out a solution that harmonizes nice theoretical properties with computational efficiency is the largest challenge. In large scale problems, solutions that have nice theoretical properties often are computationally expensive or infeasible and vice versa.

  • What is your deepest darkest fear? Please answer in the form of a question.

    Alex, what is the singularity?