From Mess to Spotless: How My Cleaner Finds the Best Route — UCS

In the previous articles, our cleaner learned how to navigate a messy house using BFS and DFS.

But there was a hidden assumption: Every move costs the same.

Real houses don’t work that way. Some rooms are easy to move through, while others are cluttered and slow the cleaner down. 🧹😩

My bedroom is usually covered with clothes and random items scattered around. Moving through it takes much more effort than moving through my tidy work area.

So, let’s make our cleaner smarter.

Instead of treating every move equally, we’ll tell it how expensive each move is.

🚶 The cost of moving between rooms.

Why BFS and DFS Are Not Enough

Both BFS and DFS ignore the cost of actions.

BFS

BFS focuses on finding the path with the fewest number of steps.

Here it doesn’t care that another Route much cheaper overall, as chosen route has smaller number of steps to goal.

DFS

Instead of exploring level by level, it keeps moving deeper into one path before considering alternatives.

The problem is that DFS also ignores costs. It may dive into an expensive path simply because that path appears first.

As a result:

• BFS minimizes the number of steps.
• DFS follows one branch deeply.
• Neither minimizes the total cost.

Our cleaner needs a new strategy.

The Cleaner’s New Focus

Instead of asking:

“Which room is closest in terms of number of moves?”

the cleaner now asks:

“Which room can I reach with the lowest total cost?”

Every time the cleaner discovers a new room, it keeps track of the total cost required to reach it from the starting position.

This accumulated cost is called the path cost to the room from the start — g(n)

Expanding the Cheapest State First

Suppose the frontier currently contains:

The cleaner chooses Room C first because it has the smallest path cost from start.

After exploring Room C, new rooms are discovered. Now Room F becomes the cheapest option.

The cleaner always selects the frontier state with the lowest accumulated cost.

This process continues until the goal is reached.

💰 Uniform Cost Search (UCS)

The strategy we have just described is called Uniform Cost Search (UCS).

🧠 Key Idea: Explore the deepest available state first before considering alternative branches.

For the engineers, the frontier behaves like a priority queue based on cost

How UCS Thinks

Notice something interesting.

UCS can compare non-goal states.

It knows that a state reached with cost 3 is preferable to one reached with cost 8.

However, UCS still does not know anything about the goal.

It only knows:

✅ How much it has already spent.

It does not know:

❌ How far the goal is.

❌ Which state is closer to the goal.

❌ Which direction looks more promising.

This is why UCS (along with BFS and DFS) is still classified as an uninformed search algorithm.

It uses cost information about the path travelled so far, but no information about the remaining distance to the goal.

Why UCS Works

Because UCS always expands the cheapest available path first:

• It never skips a cheaper alternative.
• Costs are explored in increasing order.
• A more expensive path can never be accepted before every cheaper possibility has been examined.

Therefore:

The first time the goal state is removed from the frontier, UCS has found the cheapest path to that goal.

This guarantee holds as long as all step costs are non-negative.

BFS Is Just a Special Case of UCS

What happens if every action costs exactly 1?

Then: g(n) = {number of steps}

The cheapest path becomes the same as the shortest path.

In that situation, UCS behaves exactly like BFS.

⏭️ Next Step: Best First Search

So far, our cleaner has learned three strategies.

1. **BFS: **“I don’t know costs or distance to the goal. I’ll simply explore level by level.”
2. **DFS: **“I don’t know costs or distance to the goal. I’ll keep moving deeper.”
3. **UCS: **“I know how much it costs to reach each state, so I’ll expand the cheapest one first.”

Having two states with same path cost, wouldn’t it be useful if the cleaner could estimate: “Which of these states looks closer to the goal?”

That extra piece of knowledge is called a heuristic.

That’s exactly what we’ll explore next:

Best First Search — A strategy that doesn’t just considers the cost so far — also tries to estimate how promising each state is for reaching the goal.

References

Russell, S. J., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson.