Bounded breadth-first search for agent task planning

In agent task planning, a bounded breadth-first search (BFS) takes a current state, a list of allowed actions, a completion condition, and a resource budget, and either returns the shortest action sequence that finishes the task or reports that it found none within the budget. When it finds nothing, one more check decides what that means: if the action list is declared complete, the answer is "unreachable within budget"; if the list admits it is incomplete, the answer is "unknown." This article explains that search as we implemented it in a small synthetic model from our research on how agents and people agree on a joint plan of action. The evidence is a local, finite self-test, not a deployed planner.

Zhang Chenxi (Nature), who builds agent systems for manufacturers and distributors. 22 October 2026. Drafted with AI assistance.

The problem: a switch that is off

Suppose an interface exists and the permission has been granted, but the switch is off. Ask a system whether the task can be completed, and two different answers are possible. If it tries only the operations available right now, it says no. If it may first turn the switch on and then finish the task, it finds a path.

The difference decides what the system does at an obstacle: return a failure at once, or return a specific preparation step that someone can check. Which one a planner gives depends on how its search is set up, so the rest of this article follows the setup in three parts: how the model represents completion and action preconditions, how a queue finds the path, and what a failed search can and cannot tell you.

How the model represents completion and action preconditions

The task in the research model is carried out by four execution actions: transfer, project, accept, and read back. The model also declares preparation actions, such as enabling the interface, which come up below. Read it as a simplified data-processing flow: move the data, produce the target representation, confirm that it was accepted, then read it back to check. These actions are abstract state changes inside a program. They do not mean a real service has been connected. In an agent system, the same roles fall to the tools the agent may call, the setup a tool needs before it can run, and the check the receiving side makes before it accepts a result.

Completion has concrete conditions too. Transfer and project have each happened exactly once. Accept and read back have happened. The authorization is valid, the task has not been swapped for a different one, the value floor still holds (the task does not lose value below an agreed minimum), and the budget has not been exceeded. Seeing that something "ran" is not enough, because a run can produce a result that is never accepted, or can replace the original task along the way.

The model also states when each action may be taken. Transfer needs an available route and an existing authorization. Project waits for the transfer. Accept waits for the target representation. If the interface is closed, a direct transfer has no successor state. These constraints turn "what could happen next" into something that can be checked item by item.

Written this way, the task has the same form as the problem STRIPS (Fikes and Nilsson, 1971) was built to solve: find a sequence of operators that turns a given initial world model into one where the goal can be proven true. Our model represents the state with 21 variables, each with a small, finite set of values, and searches it breadth first; STRIPS used first-order logic and a theorem prover.

How the search expands states one step at a time

The search starts from the current state and puts it in a queue. It takes the state at the front, tries each allowed action in turn, and for every action whose conditions hold, computes the new state. New states it has not seen before go to the back of the queue. Then it takes the next state from the front.

The first-in, first-out order is what matters. States reached in one step are checked before states reached in two. So if every edge is one action, the first time the search reaches the goal it has found a path with the fewest actions. This is the standard property of breadth-first search; see the BreadthFirstDirectedPaths reference implementation from the Princeton algs4 materials.

A teaching fork, separate from the recorded run, shows what the queue does. From the start there are two routes: start → A → A1 → goal and start → B → goal. Even if the search meets A first, it does not follow A all the way down. After checking the start, the queue is [A, B]. It takes A out and adds A1, so the queue becomes [B, A1]. Next comes B, which can produce the goal. The search finds the two-step route through B before the three-step route through A. The queue holds the search order, so the action listed first does not monopolize the exploration.

In a constructed scenario from the recorded run, the initial interface is closed. With only the original execution actions allowed, there is no path to completion. Add one action that already existed but had not been run, "enable the interface," and the search finds this path:

enable the interface → transfer → project → accept → read back

Those five steps replace a vague "a capability is missing" with a narrower and more useful statement. What this model lacks is an activation condition. It does not need a new way of transferring data.

The same record suggests a direct variant. Tighten the step limit from 10 to 4 and keep every action condition as it was, and the five-step route is no longer reachable. The meaning of a failed search changes with it: the task cannot be completed within four steps, which is a different claim from saying there is no way to complete it. This variant is a teaching case derived from the action preconditions. It is not a second measurement of the recorded run.

Step count and cost also need to be kept apart. A two-step route can cost more than a three-step one. This search advances layer by layer, so it finds the shorter route first. It checks whether a route's cost is within the budget, but it does not guarantee the lowest cost among all feasible routes. In the recorded model every action costs 1, so the fewest steps and the lowest cost coincide there. When you need the lowest cost, use a weighted shortest-path method and state the conditions on edge costs.

What "bounded" says: unreachable within budget versus an incomplete action list

A finite search can finish because we drew boundaries around it. The recorded run set a limit of 10 steps, a cost limit of 10, a privacy-cost limit of 2 (looking into other parties' hidden state uses this budget), and at most one escalation to a person. The available actions and state variables were also finite. As actions multiply and paths get longer, the number of possible states grows quickly. These budgets decide which question the model is answering. In the ten recorded worlds they never cut the search short: each action can happen only a limited number of times, so every search ended, by finding a path or running out of new states, before any limit came into play. In larger models the budgets are also what keeps the computation small.

When the search finds a path inside those bounds, you can hand over the full action sequence and check each precondition and state change. When it finds none, you still need to check whether the action list is complete.

If the list is declared complete and every allowed state has been searched, the model reports "unreachable within budget." If the list itself admits it is incomplete, the model returns "unknown." For example, in practice someone might be asked to build a new tool, but the model does not list how to build it, whose consent is needed, or what it would cost. A search that finds no path cannot rule out a route that has not been written down.

Reading a failed search as "no path exists" applies the closed world assumption (Reiter, 1978): when no proof of a fact can be found, the fact is taken to be false. The model applies it only when the action list is declared complete, and even then it concludes only that no path exists within the budget.

The model itself returns only a path or a verdict, but the distinction points people to different next steps. If the budget is too tight, people can discuss raising it. If a precondition is closed, they can check whether it can be activated. If the action list is incomplete, someone needs to add the options that are really available. Writing every case as "failure" removes all three directions at once.

Results on synthetic worlds: six solvable, three unreachable, one unknown

The recorded experiments built ten small worlds and ran three scheduling variants with the same action capabilities on them. The variants are rule-based planners, not searches: one works backward from the goal, one follows a fixed exception-routing workflow, and the third is our candidate for a new scheduling method. Each looked at the world once, then either ran its plan or stopped. All three completed the task in the same six worlds and stopped in the other four. The bounded search decided what those four stops mean: three are unreachable within budget, and one is unknown because that world's action list is declared incomplete. None of the three unreachable worlds is a budget problem: in one the value floor has already failed; in another the owner refuses; in the third the owner refuses too, and the route is unavailable and cannot be enabled. The candidate solved no world that the other two could not. The three variants share an implementation base, so this is not validation by three independent systems.

The result does not support the claim that a new scheduling algorithm is needed to solve these tasks. It supports a narrower design judgment: once preparation actions, authorization conditions, and the completion criterion are written into one model, plain breadth-first search can already separate some obstacles that look the same when first reported. The hard part is often whether the conditions that can change have been expressed at all.

Reality is far more complicated than ten small worlds. People can refuse, actions can fail, and new tools can appear. A finite model cannot cover all of that. But when you need to examine one specific process, a five-step witness path, the concrete action sequence the search returns to show the task can be finished, is more useful than "it can be done in theory": each step invites a follow-up question about who provides the precondition, whether the step can actually be run, and how to confirm it afterward. Those questions are where the research can next be checked against real processes.

Where the evidence comes from

The search implementation, the state and action model, and the raw search output all come from our research code.

We built this search within ToWow's research on agents that coordinate work between people. If you work on agent task planning and want to compare notes, write to hi@towow.ai.

An earlier Chinese version of this article is at towow.net/articles/towow-backward-chain-planning.

If you want a system like this built around your own workflow, see AI agent systems for manufacturers and distributors or write to hi@towow.ai.