Algorithms for Path-Planning

Consider a robot with a map of its environment, that needs to visit a number of sites to deliver packages, collect samples, etc. However, owing to a limited supply of battery power, or some unforeseen obstacle, the robot may not be able to visit all the sites. In such a situation, a natural goal is to ask for a tour that visits as many sites as possible by some pre-determined deadline. This is the classic Orienteering problem. More generally, path-planning problems involve ordering and performing a set of tasks (or visiting locations) as efficiently as possible, while obeying constraints such as deadlines. These problems arise in many fields including operations research, scheduling, and robotics, and are mostly NP-hard. In this talk I will present the first approximations to several path-planning problems including Orienteering. I will then extend the path-planning framework to deal with uncertainty (such as that arising in a robot\'s environment), and describe how the previous algorithms can be applied to robot navigation. I will conclude with a brief discussion of new paradigms for optimization, specifically, dealing with private information and game-theoretic scenarios.