Large Language Models (LLMs) have demonstrated impressive planning abilities
due to their vast "world knowledge". Yet, obtaining plans that are both
feasible (grounded in affordances) and cost-effective (in plan length), remains
a challenge, despite recent progress. This contrasts with heuristic planning
methods that employ domain knowledge (formalized in action models such as PDDL)
and heuristic search to generate feasible, optimal plans. Inspired by this, we
propose to combine the power of LLMs and heuristic planning by leveraging the
world knowledge of LLMs and the principles of heuristic search. Our approach,
SayCanPay, employs LLMs to generate actions (Say) guided by learnable domain
knowledge, that evaluates actions' feasibility (Can) and long-term
reward/payoff (Pay), and heuristic search to select the best sequence of
actions. Our contributions are (1) a novel framing of the LLM planning problem
in the context of heuristic planning, (2) integrating grounding and
cost-effective elements into the generated plans, and (3) using heuristic
search over actions. Our extensive evaluations show that our model surpasses
other LLM planning approaches.

结合大型语言模型和启发式规划的方法，该研究提出了一种通过利用大型语言模型的世界知识和启发式搜索原则来生成行动序列的新方法，该方法能够在规划过程中考虑行动的可行性和成本效益，评估行动的长期效果，并在广泛的评估中显示优于其他大型语言模型规划方法。

SayCanPay: 基于可学习领域知识的大型语言模型的启发式规划

SayCanPay: Heuristic Planning with Large Language Models using Learnable  Domain Knowledge

Current evaluation functions for heuristic planning are expensive to compute.
In numerous planning problems these functions provide good guidance to the
solution, so they are worth the expense. However, when evaluation functions are
misguiding or when planning problems are large enough, lots of node evaluations
must be computed, which severely limits the scalability of heuristic planners.
In this paper, we present a novel solution for reducing node evaluations in
heuristic planning based on machine learning. Particularly, we define the task
of learning search control for heuristic planning as a relational
classification task, and we use an off-the-shelf relational classification tool
to address this learning task. Our relational classification task captures the
preferred action to select in the different planning contexts of a specific
planning domain. These planning contexts are defined by the set of helpful
actions of the current state, the goals remaining to be achieved, and the
static predicates of the planning task. This paper shows two methods for
guiding the search of a heuristic planner with the learned classifiers. The
first one consists of using the resulting classifier as an action policy. The
second one consists of applying the classifier to generate lookahead states
within a Best First Search algorithm. Experiments over a variety of domains
reveal that our heuristic planner using the learned classifiers solves larger
problems than state-of-the-art planners.

本文提出了一种基于机器学习的启发式计划搜索控制方法，通过学习搜索启发式计划的控制策略，实现了减少计算节点评估的目的，并通过两种方法（使用分类器作为行动策略和将分类器应用于生成前瞻状态）有效提高搜索效率，解决了现有启发式计划算法在可伸缩性方面的不足。

使用关系决策树扩展启发式规划

Scaling up Heuristic Planning with Relational Decision Trees

In a Role-Playing Game, finding optimal trajectories is one of the most
important tasks. In fact, the strategy decision system becomes a key component
of a game engine. Determining the way in which decisions are taken (online,
batch or simulated) and the consumed resources in decision making (e.g.
execution time, memory) will influence, in mayor degree, the game performance.
When classical search algorithms such as A* can be used, they are the very
first option. Nevertheless, such methods rely on precise and complete models of
the search space, and there are many interesting scenarios where their
application is not possible. Then, model free methods for sequential decision
making under uncertainty are the best choice. In this paper, we propose a
heuristic planning strategy to incorporate the ability of heuristic-search in
path-finding into a Dyna agent. The proposed Dyna-H algorithm, as A* does,
selects branches more likely to produce outcomes than other branches. Besides,
it has the advantages of being a model-free online reinforcement learning
algorithm. The proposal was evaluated against the one-step Q-Learning and
Dyna-Q algorithms obtaining excellent experimental results: Dyna-H
significantly overcomes both methods in all experiments. We suggest also, a
functional analogy between the proposed sampling from worst trajectories
heuristic and the role of dreams (e.g. nightmares) in human behavior.

本论文提出了一种基于启发式规划策略的路径规划方法，该方法在模型自由的在线强化学习中比传统的单步 Q 学习和 Dyna-Q 算法都表现出色，可以用于角色扮演游戏中的最优轨迹规划。