Mapping UC Berkeley
I led a team of three at the UC Berkeley Pre-College Computer Science Summer Institute. The code stayed with the program, so there is nothing to link.
problem
The shortest path across a campus is not always the route a person wants to walk. We kept returning to the same case: a route that is fine at noon is one somebody would refuse at eleven at night. A router that only minimizes distance has no way to express that.
approach
We modeled the campus as a weighted graph of paths and intersections and ran A* over it, using straight line distance as the heuristic. That heuristic is admissible by construction, since no path between two points can be shorter than the line between them, so the route A* returns is genuinely optimal.
The part we cared about was the avoid feature. A user selects regions of campus to exclude, and the search runs against a graph with those nodes already removed rather than penalised during the search.
tradeoffs
- choice Excluded areas come out of the graph entirely. They are not just made expensive.cost Removal means avoid actually means avoid, so the router can never quietly decide that cutting through is worth the saving. It also means a large exclusion can disconnect the graph, which we then had to handle as a real outcome instead of an edge case.
- choice Straight line distance as the heuristic, with nothing tuned or learned on top.cost Admissible by construction, so we never had to argue about whether the heuristic was lying to us. On a campus with few long detours it also expands more nodes than a tighter heuristic would.
what broke
Routes went through the zones people had told it to avoid. The first version handled an exclusion by giving those nodes a very high cost, and we assumed a cost that high meant nothing would ever cross one.
A* crossed them anyway, whenever going around was expensive enough to be worth it. On a campus that is most of the time, because the detour around a closed off block is long and the block itself is short. A high price is still a price, and the search was doing exactly what we had asked.
Taking the nodes out of the graph before the search starts was the fix, which is why exclusion is a hard constraint now instead of an expensive suggestion.
what I learned
A penalty is not a constraint. If a rule has to hold, it belongs in the graph, not in the cost function, because anything expressed as a cost is something the search is allowed to buy.
We fixed the graph representation on the first day. That is the only reason three of us could work on it in parallel for a week.