This project involves developing connections between Approximation Algorithms, Machine Learning and AI problems of planning under uncertainty. This work has two main related themes. The first is extending the technology of approximation algorithms to problems of greater interest to AI and Robotics. These include problems of path planning under uncertainty, clustering, and problems motivated by new challenges in machine learning. For instance, in the context of path planning, the classic Traveling Salesman Problem asks: what is the shortest route to visit all locations of interest in some deterministic environment and return back to the start? But what if we are developing a plan for a robot whose actions may be unreliable and to which unexpected events can occur? In that case, we would want to use a stochastic model of the environment such as in Markov Decision Processes. Can one develop good approximations to the natural analog of the TSP in such settings? One of the goals of this work is to explore this and several related optimization problems. In a different context, in machine learning there are a number of problems that can be phrased as a form of graph partitioning, but where the graph is embedded in Rn and there is some geometric restriction on the form of cuts allowed.
The second theme of this work is in the other direction, applying techniques from computational learning theory, including online learning and sample-complexity analysis, to the design of algorithms for optimization problems with provable quality guarantees. These include problems in routing, in algorithmic mechanism design, and a number of problems in online optimization.
Other topics in this proposal include the exploring the relation between kernel methods in machine learning and dimensionality reduction, and investigating how online learning techniques can be used to converge to certain game-theoretic equilibria. The intellectual merit of the proposed work is that this research will advance our understanding of important problems in all three areas: approximation algorithms, machine learning, and planning under uncertainty. The broader impact is that by developing connections between these areas, it will bring them closer together, for instance by developing algorithms with good approximation guarantees for models of greater interest to robotics, or algorithms for clustering and graph partitioning problems of greater interest to machine learning. This will in turn, we hope, allow future work by other researchers in each area to have a greater impact on each of the other areas.
