Directed by:
Alexander Vladimirsky
Please note: What follows is a list of "model problems". These are just several representative examples meant to illustrate the above challenges, rather than the exact problems to be attacked during this REU.
A robot is trying to navigate through a room with many obstacles. The goal is to reach the target using as little energy as possible, while also minimizing the total time the robot is seen by an enemy observer (whose location may or may not be known in advance).
Given a smooth two dimensional surface, how can one efficiently compute the geodesic distances between any two points on it? (The "geodesic distance" is the minimal distance of travel for an ant crawling on that surface between the specified points.)
Suppose that our ant already knows the geodesic distances between all pairs of surface points. Is that enough information to guess the shape of that surface? If only some of the pairwise distances are known, what is the best guess about the surface shape? (The humans have solved a simple version of this problem, when they first realized that the Earth is more or less spherical.)
A Homicidal Chauffeur tries to run over a Pedestrian. The Chauffeur's speed is much greater, but he is constrained by the minimum turn-radius. Can the Pedestrian survive this encounter? ... in the presence of obstacles? ... until the arrival of Police?
Given a list of most common emergency-caller locations and the frequency of calls originating at each of them, what would be the best place to build an ambulance depot? Suppose an "idle ambulance" starts somewhere else on the map in between emergency calls. If the goal is to minimize the expected waiting time of the next caller, should that ambulance stay at its current position or start moving toward the depot? If the latter, what path should it choose? How will the optimal strategy depend on the total number of ambulances?
Given a map of the Treasure Island with complicated terrain and a list of 50 different locations where the treasure could be buried, what is the best path to follow if you want to minimize the expected time until you find that treasure?
A sophomore student is trying to decide on which courses to take in her 3rd semester. She definitely needs to graduate at the end of her 4th year, and the graduation requirements are known. However, due to the budgetary crisis, not all courses are offered every year, the enrollment is limited, and the prerequisites are rigorously enforced. We assume that she can predict reasonably well how much she would like or dislike each course; i.e., the "utility" of each course is quantifiable and known. Suppose that the probability of each course being offered is also known for each of the future semesters. Which courses should she take right now to maximize her expected total utility up to the graduation? Which courses should she take instead if the goal is to optimize "the worst case scenario"? What is "the best on average" plan if she wants to enforce a particular lower bound on "the worst case scenario" ?