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 question 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 a set of locations to be visited, with constraints on the path taken to visit them, such as deadlines on visiting particular locations, or a minimum number of locations that must be visited. 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 discuss an application of path-planning to robot navigation and describe the complications that arise due to uncertainty in the robot's environment.