Cornell REU Project:   Optimality and Uncertainty   (Summer 2022).

Directed by: Alexander Vladimirsky

• "Optimal Control Theory" describes methods for finding "the best" strategy to reach the specified goals given your initial situation.

• The world through which you travel toward your goals can be discrete (e.g., when finding the shortest path between two nodes on a graph - think of the algorithms that compute your driving directions within a city) or continuous (e.g., think of a rover traveling through mixed terrain on Mars).

• In the latter case, the conditions expressing the optimality of your strategy are represented by differential equations. Numerical solutions of these differential equations can be very expensive computationally.

• "Differential Games" represent a more general case, where the evolution of the system is influenced by two players with opposite goals - one is trying to minimize a certain cost, while the other attempts to maximize it.

• Uncertainty, random events, and conflicting goals will make it even harder to determine the optimal strategy.

• We will work to build and analyze fast algorithms for optimal control and differential games.

• Successful participants will need programming skills, at least some prior experience with numerical computing, and exposure to ordinary differential equations.

• Some background in PDEs, probability theory, and game theory would be also useful, but certainly is not required or expected. We will provide a brief introduction to the relevant parts of these subjects during the first weeks of the program.

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" ?

Back to the Main Page of Cornell REU Projects