Planning under time pressure arises in many situations. Real-time heuristic search, in which an agent must compute its next action within a prespecified time bound, has proven to be a useful model of real-time planning. However, it is laborious to prove the completeness of new real-time search algorithms. In this paper, we provide a general proof of the completeness of a standard real-time heuristic search algorithm in any problem domain that obeys the axioms of a cost algebra. The proof includes additional detail on how h values change as the algorithm learns. This foundation clarifies the dependence of the proof on domain and algorithm properties and will ease future applications of real-time planning.

Train routing is sensitive to delays that occur in the network. When a train is delayed, it is imperative that a new plan be found quickly, or else other trains may need to be stopped to ensure safety, potentially causing cascading delays. In this paper, we consider this class of multi-agent planning problems, which we call Multi-Agent Execution Delay Replanning. We show that these can be solved by reducing the problem to an any-start-time safe interval planning problem. When an agent has an any-start-time plan, it can react to a delay by simply looking up the precomputed plan for the delayed start time. We identify crucial real-world problem characteristics like the agent's speed, size, and safety envelope, and extend the any-start-time planning to account for them. Experimental results on real-world train networks show that any-start-time plans are compact and can be computed in reasonable time while enabling agents to instantly recover a safe plan.

Navigation among dynamic obstacles is a fundamental task in robotics that has been modeled in various ways. In Safe Interval Path Planning, location is discretized to a grid, time is continuous, future trajectories of obstacles are assumed known, and planning takes place offline. In this work, we define the Real-time Safe Interval Path Planning problem setting, in which the agent plans online and must issue its next action within a strict time bound. Unlike in classical real-time heuristic search, the cost-to-go in Real-time Safe Interval Path Planning is a function of time rather than a scalar. We present several algorithms for this setting and prove that they learn admissible heuristics. Empirical evaluation shows that the new methods perform better than classical approaches under a variety of conditions.

Traditionally when planning we assume that we receive the problem instance as input, then formulate a plan, then the clock begins and the agent executes the plan. Sometimes we are forced to consider time passing as we plan, which is known as situated planning. In my dissertation I explore situated planning in three domains: grid based path planning, the orienteering problem and opportunistic science.

There has been much recent work on finding paths in grid maps among moving obstacles. However, in addition to assuming complete omniscience regarding the map and the obstacles' trajectories, previous work has also assumed that time stands still while the agent plans. In this paper, we address situated pathfinding, in which time passes and the obstacles continue to move while the agent plans. We study the choice of state space representation and search algorithm, with a focus on whether conclusions drawn from studies in the off-line case continue to hold in a situated setting.