[March 24th, 2025] update some content

[Sep. 20th, 2024] I finished a simple version, some details are not illustrated here, and more future directions still need more thinking and precipitation.

Too much content to include, and procrastination ☹️. I will finish this in August, 2024.

As I discussed MCTS and its application in AlphaGo Zero, this blog will discuss more ideas about search, MCTS, rl in Large Language Model Planning, which may offers some inspiration in better solving LLM agent planning problems. This blog is still in process, I will finish this in July, 2024.

Planning

What is Planning?

Planning involves developing a course of actions which when executed takes the agent to a desired state of world.

image.png

There are some core modules in planning:

<aside> 📌 You may find these elements are similar to those in reinforcement learning. But the main difference is that in rl, the agent always execute the actions and then reach another state, but in planning, actions are always not executed (but can be executed in a simulation env).

</aside>

How to solve a planning problem?

Traditional planning, especially symbolic planning, holds discrete states and deterministic transitions. They can be described in Planning Domain Description Language (PDDL), which is a formal language of planning problem based on formal logic. And for problems described in PDDL, there are AI planners (e.g., Fast-Forward planner (FF), BFS(f) planner) to find the optimal plan.

However, although those AI planners can solve planning problems in well-defined domains, they require complete information and domain descriptions, leading to their limitations in complex world.

LLM for Planning?

We wonder to know whether LLM generates plans by itself. According to previous work, it is hard for LLM to autonomously generate executable plans without any external tools.

On the Planning Abilities of Large Language Models: A Critical Investigation (NeurIPS 2023)

On the Planning Abilities of Large Language Models: A Critical Investigation (NeurIPS 2023)

LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks

LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks

However, LLM and some optimal planners are complementary for solving such questions.