Is step cost always one?

No. Unit step costs are a special case that makes path cost equal to action count.

Can a cost depend on the action's outcome?

Yes. A transition-cost notation can include the successor state; uncertain outcomes require an appropriate decision model.

Does changing units alter the best route?

Multiplying all costs by the same positive factor preserves ordering. Adding a fixed amount to every step can change it.

AI Glossary / Graphs and symbolic AI / Intermediate

Step cost

Definition

A step cost is the cost assigned to a single action or transition in a search problem. It measures what is incurred when moving from one state to a successor state through that action. When the problem uses additive costs, the total cost of a path is the sum of its individual step costs.

What it means

The cost need not be money. It can represent travel time, distance, energy use, or a deliberately defined penalty. Its units and meaning must be consistent with the problem's objective.
Step cost is distinct from the number of steps. Two routes with the same number of actions can have different total costs, and a longer route can be cheaper than a shorter one. It is also distinct from the computational effort used to search for the route. A planner might spend considerable computation finding a plan whose modeled execution cost is low.

How it works

Define a cost for each permitted transition, often written c(s, a, s'), where s is the current state, a is the action, and s' is the resulting state. For an additive objective, extend a path by updating its accumulated cost: new cost equals previous cost plus the new step cost.
Search algorithms use these values differently. Uniform-cost search selects candidates by accumulated path cost, whereas breadth-first search selects by depth. An informed method can combine the accumulated cost with an estimate of the remaining cost. The model must represent any information that changes future costs; otherwise the same apparent transition can be assigned an inappropriate value.

Three practical examples

A route planner can assign each road segment a travel-time cost under a stated traffic model.
A robot planner can assign movement and handling actions energy costs, provided the resulting objective is defined consistently.
A workflow prototype can assign processing-time costs to actions and compare alternative sequences that achieve the same goal.

Think of it this way

Think of a receipt with one charge for each item purchased. Adding the line items gives the total under that pricing model. The analogy is limited because some real costs involve discounts, shared overheads, or interactions; these cannot always be represented correctly by fixed independent charges without a richer state or objective.

Worked example

Consider an original directed routing graph with start S and goal G. The available edges and step costs are S→A with cost 2, A→G with cost 8, S→B with cost 3, B→C with cost 2, and C→G with cost 2. There are no other edges.
Route S - A - G has two steps and costs 2 + 8 = 10. Route S - B - C - G has three steps and costs 3 + 2 + 2 = 7. The three-step route is cheaper, so minimizing the number of steps would not minimize this cost.
Trace a uniform-cost search that tests a goal when its cheapest candidate is removed from the frontier. After expanding S, the frontier contains A at accumulated cost 2 and B at cost 3. Expanding A adds a goal candidate at cost 10. The search does not stop merely because that goal has been generated.
It next selects B at cost 3 and generates C at cost 5. Selecting C then generates a goal path at cost 7. That candidate is selected before the cost-10 alternative, giving the cheaper solution. A graph implementation may update an existing goal record or retain candidates with a stale-entry check; either approach must preserve the better path.
Now multiply every edge cost by four. The two route costs become 40 and 28, and their ordering is unchanged. In contrast, add four to every edge cost. The two-step route becomes 10 + 8 = 18, while the three-step route becomes 7 + 12 = 19. The preferred route reverses.
This happens because adding a constant per step changes the penalty for taking more steps. It is not merely a change of units. The distinction matters when a team adds a fixed handling charge or action penalty to an existing model.

Illustrative case study

In a fictional warehouse-routing project, a team initially minimizes the number of moves. It later finds that some moves involve slow handling operations while others are simple transfers.
The team defines action costs using the intended operational measure and checks complete route totals against small manually reviewed examples. It also examines whether load status affects those costs and adds that information to the state when necessary. This fictional case illustrates model design rather than claiming measured savings.

Common misconceptions and mistakes

A small step cost does not guarantee a small total cost, because many steps may follow. Likewise, choosing the cheapest next action is not generally the same as choosing the cheapest complete path.
Do not combine minutes, currency, and energy into one sum without defining a meaningful conversion or preference model. Do not assume familiar search guarantees survive negative costs. Finally, if actions overlap in time, adding their durations may not equal total completion time; the objective and state representation must reflect the scheduling structure.

Business use

Step costs make a planner's priorities inspectable. They show what the system treats as expensive and help explain why it selects a particular route or workflow.
Review the cost units, data sources, and assumptions with the people who own the process. Test whether fixed costs hide dependencies such as load, setup, or congestion. When comparing algorithms, keep the cost model fixed so that a better reported result reflects the search behavior rather than a changed definition of what the business values.

Check your understanding

Why does adding four to every edge cost reverse the preferred route in the example?

Answer: The three-step route receives three extra charges, while the two-step route receives only two. Their totals become 19 and 18 respectively.

Related terms

Uniform-cost search
Breadth First Search
Transition model
Shortest Paths
Path cost
Action cost
Cost function
Heuristic estimate
Shortest path

Learn next

Next, add a per-step charge k to the original routes. Their costs become 10 + 2k and 7 + 3k. Solve for equality: k = 3. Below that value the three-step route is cheaper; above it the two-step route is cheaper. Explain what the crossing point means for the modeled decision.

Sources

Primary sources: Berkeley CS188, State Spaces and Search Problems: https://inst.eecs.berkeley.edu/~cs188/textbook/search/state.html ; and Uninformed Search: https://inst.eecs.berkeley.edu/~cs188/textbook/search/uninformed.html . The routing graph, frontier trace, and cost-transformation calculations are original.

Previous: Stemming Next: Step size