One key decision for heuristic search algorithms is how to balance
exploration and exploitation. In classical planning, novelty search has come
out as the most successful approach in this respect. The idea is to favor
states that contain previously unseen facts when searching for a plan. This is
done by maintaining a record of the tuples of facts observed in previous
states. Then the novelty of a state is the size of the smallest previously
unseen tuple. The most successful version of novelty search is best-first width
search (BFWS), which combines novelty measures with heuristic estimates. An
orthogonal approach to balance exploration-exploitation is to use several
open-lists. These open-lists are ordered using different heuristic estimates,
which diversify the information used in the search. The search algorithm then
alternates between these open-lists, trying to exploit these different
estimates. This is the approach used by LAMA, a classical planner that, a
decade after its release, is still considered state-of-the-art in agile
planning. In this paper, we study how to combine LAMA and BFWS. We show that
simply adding the strongest open-list used in BFWS to LAMA harms performance.
However, we show that combining only parts of each planner leads to a new
state-of-the-art agile planner.

如何将最成功的 BFWS 与经典规划器 LAMA 相结合，我们研究表明，将 BFWS 中强大的 open-list 直接添加到 LAMA 中会降低其性能，但将两者的部分特征相结合却能产生一种新的最先进的敏捷规划器。

将 LAMA 与最佳优先宽度搜索相结合

Consolidating LAMA with Best-First Width Search

For combinatorial optimization problems, model-based paradigms such as
mixed-integer programming (MIP) and constraint programming (CP) aim to decouple
modeling and solving a problem: the `holy grail' of declarative problem
solving. We propose domain-independent dynamic programming (DIDP), a new
model-based paradigm based on dynamic programming (DP). While DP is not new, it
has typically been implemented as a problem-specific method. We introduce
Dynamic Programming Description Language (DyPDL), a formalism to define DP
models based on a state transition system, inspired by AI planning. We show
that heuristic search algorithms can be used to solve DyPDL models and propose
seven DIDP solvers. We experimentally compare our DIDP solvers with commercial
MIP and CP solvers (solving MIP and CP models, respectively) on common
benchmark instances of eleven combinatorial optimization problem classes. We
show that DIDP outperforms MIP in nine problem classes, CP also in nine problem
classes, and both MIP and CP in seven.

基于动态规划 (DP) 的领域无关动态规划 (DIDP) 模型具有优于其他方法的性能，通过引入七种 DIDP 求解器和对 11 种组合优化问题类别的基准测试，实验证明 DIDP 在大部分问题类别中优于混合整数规划 (MIP) 和约束规划 (CP)。

领域无关动态规划

Domain-Independent Dynamic Programming

Heuristic search algorithms, e.g. A*, are the commonly used tools for
pathfinding on grids, i.e. graphs of regular structure that are widely employed
to represent environments in robotics, video games etc. Instance-independent
heuristics for grid graphs, e.g. Manhattan distance, do not take the obstacles
into account and, thus, the search led by such heuristics performs poorly in
the obstacle-rich environments. To this end, we suggest learning the
instance-dependent heuristic proxies that are supposed to notably increase the
efficiency of the search. The first heuristic proxy we suggest to learn is the
correction factor, i.e. the ratio between the instance independent cost-to-go
estimate and the perfect one (computed offline at the training phase). Unlike
learning the absolute values of the cost-to-go heuristic function, which was
known before, when learning the correction factor the knowledge of the
instance-independent heuristic is utilized. The second heuristic proxy is the
path probability, which indicates how likely the grid cell is lying on the
shortest path. This heuristic can be utilized in the Focal Search framework as
the secondary heuristic, allowing us to preserve the guarantees on the bounded
sub-optimality of the solution. We learn both suggested heuristics in a
supervised fashion with the state-of-the-art neural networks containing
attention blocks (transformers). We conduct a thorough empirical evaluation on
a comprehensive dataset of planning tasks, showing that the suggested
techniques i) reduce the computational effort of the A* up to a factor of $4$x
while producing the solutions, which costs exceed the costs of the optimal
solutions by less than $0.3$% on average; ii) outperform the competitors, which
include the conventional techniques from the heuristic search, i.e. weighted
A*, as well as the state-of-the-art learnable planners.

本文提出了一种使用神经网络学习实例依赖的启发式代理来提高在障碍物环境下的 A * 算法性能的方法，并针对该算法进行了全面实验评估，结果表明该算法在减少计算量和保证较小的解代价方面具有优异的性能。

TransPath：通过 Transformer 学习基于网格的路径搜索算法启发式

TransPath: Learning Heuristics For Grid-Based Pathfinding via  Transformers

Stochastic Shortest Path (SSP) MDPs is a problem class widely studied in AI,
especially in probabilistic planning. They describe a wide range of scenarios
but make the restrictive assumption that the goal is reachable from any state,
i.e., that dead-end states do not exist. Because of this, SSPs are unable to
model various scenarios that may have catastrophic events (e.g., an airplane
possibly crashing if it flies into a storm). Even though MDP algorithms have
been used for solving problems with dead ends, a principled theory of SSP
extensions that would allow dead ends, including theoretically sound algorithms
for solving such MDPs, has been lacking. In this paper, we propose three new
MDP classes that admit dead ends under increasingly weaker assumptions. We
present Value Iteration-based as well as the more efficient heuristic search
algorithms for optimally solving each class, and explore theoretical
relationships between these classes. We also conduct a preliminary empirical
study comparing the performance of our algorithms on different MDP classes,
especially on scenarios with unavoidable dead ends.

本文提出了三种新的 MDP 类，允许无法到达的目标，并呈现了具有理论基础的算法，探讨了这些类之间的理论关系，并进行了初步的实证研究。