Empirically, this optimization lead to 0.5 - 2.5% savings on expansions in our experiments A fundamental concern in real-time planning is the presence (Cserna, Gall, and Ruml 2019). of dead-ends in the state space, from which no goal is reachable. SafeRTS interleaves exploration and safety proofs during Providing real-time heuristic search algorithms that are its planning phase. As a direct consequence, it attempts complete in domains with dead-end states is a challenging safety proofs on nodes that become internal to the LSS by problem. Recently, the SafeRTS algorithm was proposed for the end of the search iteration. As shown in Cserna, Gall, and searching in such spaces (Cserna et al. 2018). SafeRTS exploits Ruml (2019), it would be equally or less difficult to achieve a user-provided predicate to identify safe states, from the same or better safety coverage by doing safety proofs after which a goal is likely reachable, and attempts to maintain a all the LSS expansions. SafeRTS has an anytime behavior backup plan for reaching a safe state at all times.

PLRTA* conflates all states that differ only in time into a single abstract state. Abstract states inherit the union of all In dynamic environments such as cities, agents often do not the predecessors of their preimage states, so that backups have time to find a complete plan to reach a goal state. Planning can be performed properly. PLRTA* learns a single static in such environment requires an agent to update its plan heuristic value for each abstract state. For dynamic learning, frequently to respond to the changes around it. The setting PLRTA* performs the standard Dijkstra-style backup across of real-time heuristic search models online planning by requiring the LSS, considering only costs arising from the dynamic elements the agent to commit to its next action within a strict of the environment. As presented by Cannon, Rose, time limit. The time bound for planning is set to the time and Ruml (2014), the algorithm commits to only one step at which the actions to which the agent has already committed along the selected path, and then replans using updated information.

A fundamental concern in real-time planning is the presence of dead-ends in the state space, from which no goal is reachable. Recently, the SafeRTS algorithm was proposed for searching in such spaces. SafeRTS exploits a user-provided predicate to identify safe states, from which a goal is likely reachable, and attempts to maintain a backup plan for reaching a safe state at all times. In this paper, we study the SafeRTS approach, identify certain properties of its behavior, and design an improved framework for safe real-time search. We prove that the new approach performs at least as well as SafeRTS and present experimental results showing that its promise is fulfilled in practice.

Real-time agent-centered heuristic search is a well-studied problem where an agent that can only reason locally about the world must travel to a goal location using bounded computation and memory at each step. Many algorithms have been proposed for this problem and theoretical results have also been derived for the worst-case performance with simple examples demonstrating worst-case performance in practice. Lower bounds, however, have not been widely studied. In this paper we study best-case performance more generally and derive theoretical lower bounds for reaching the goal using LRTA*, a canonical example of a real-time agent-centered heuristic search algorithm. The results show that, given some reasonable restrictions on the state space and the heuristic function, the number of steps an LRTA*-like algorithm requires to reach the goal will grow asymptotically faster than the state space, resulting in ``scrubbing'' where the agent repeatedly visits the same state. We then show that while the asymptotic analysis does not hold for more complex real-time search algorithms, experimental results suggest that it is still descriptive of practical performance.

Real-time heuristic search is suitable for time-sensitive pathfinding and planning tasks when an AI-controlled non-playable character must interleave its planning and plan execution. Since its inception in the early 90s, numerous real-time heuristic search algorithms have been proposed. Many of the algorithms also have control parameters leaving a practitioner with a bewildering array of choices. Recent work treated the task of algorithm and parameter selection as a search problem in itself. Such automatically found algorithms outperformed previously known manually designed algorithms on the standard video-game pathfinding benchmarks. In this paper we follow up by selecting an algorithm and parameters automatically per map. Our sampling-based approach is efficient on the standard video-game pathfinding benchmarks. We also apply the approach to per-problem algorithm selection and while it is effective there as well, it is not practical. We offer suggestions on making it so.

Real-time heuristic search models an autonomous agent solving a search task. The agent operates in a real-time setting by interleaving local planning, learning and move execution. In this paper we propose a simple parametric algorithm that combines weighting with learning from multiple neighbors. Doing so breaks heuristic admissibility but allows the agent to escape heuristic depressions more quickly. We prove completeness of the algorithm and empirically compare it to several competitors more than twenty years apart. In a large-scale evaluation the new algorithm found better solutions than the recent algorithms, despite not learning additional information that they do. Finally, we study robustness of the algorithms to noise in the heuristic function — a desirable property in a physical implementation of real-time heuristic search. The new algorithm outperforms its contemporaries.

In real-time domains such as video games, planning happens concurrently with execution and the planning algorithm has a strictly bounded amount of time before it must return the next action for the agent to execute. We explore the use of real-time heuristic search in two benchmark domains inspired by video games. Unlike classic benchmarks such as grid pathfinding and the sliding tile puzzle, these new domains feature exogenous change and directed state space graphs. We consider the setting in which planning and acting are concurrent and we use the natural objective of minimizing goal achievement time. Using both the classic benchmarks and the new domains, we investigate several enhancements to a leading real-time search algorithm, LSS-LRTA*. We show experimentally that 1) it is better to plan after each action or to use a dynamically sized lookahead, 2) A*-based lookahead can cause undesirable actions to be selected, and 3) on-line de-biasing of the heuristic can lead to improved performance. We hope this work encourages future research on applying real-time search in dynamic domains.

Real-time agent-centered heuristic search is a well-studied problem where an agent that can only reason locally about the world must travel to a goal location using bounded computation and memory at each step. Many algorithms have been proposed for this problem, and theoretical results have also been derived for the worst-case performance. Assuming sufficiently poor tie-breaking, among other conditions, we derive theoretical best-case bounds for reaching the goal using LRTA*, a canonical example of a real-time agent-centered heuristic search algorithm. We show that the number of steps required to reach the goal can grow asymptotically faster than the state space, resulting in a "scrubbing" when the agent repeatedly visits the same state. This theoretical result, supported by experimental data, encourages recent work in the field that uses novel tie-breaking schemas and/or perform different types of learning.

Heuristics used for solving hard real-time search problems have regions with depressions. Such regions are bounded areas of the search space in which the heuristic function is exceedingly low compared to the actual cost to reach a solution. Real-time search algorithms easily become trapped in those regions since the heuristic values of states in them may need to be updated multiple times, which results in costly solutions. State-of-the-art real-time search algorithms like LSS-LRTA*, LRTA*(k), etc., improve LRTA*'s mechanism to update the heuristic, resulting in improved performance. Those algorithms, however, do not guide search towards avoiding or escaping depressed regions. This paper presents depression avoidance, a simple real-time search principle to guide search towards avoiding states that have been marked as part of a heuristic depression. We apply the principle to LSS-LRTA* producing aLSS-LRTA*, a new real-time search algorithm whose search is guided towards exiting regions with heuristic depressions. We show our algorithm outperforms LSS-LRTA* in standard real-time benchmarks. In addition we prove aLSS-LRTA* has most of the good theoretical properties of LSS-LRTA*.

Real-time search is a well known approach to solving search problems under tight time constraints. Recently, it has been shown that LSS-LRTA∗ , a well-known real-time search algorithm, can be improved when search is actively guided away of depressions. In this paper we investigate whether or not RTAA∗ can be improved in the same manner. We propose aRTAA∗ and daRTAA∗ , two algorithms based on RTAA∗ that avoid heuristic depressions. Both algorithms outperform RTAA∗ on standard path-finding tasks, obtaining better-quality solutions when the same time deadline is imposed on the duration of the planning episode. We prove, in addition, that both algorithms have good theoretical properties.