6.4 A Set of Searching Tools The GPS program can be seen as a problem in search. In general, a search problem involves exploring from some starting state and investigating neighboring states until a solution is reached. As in GPS, state means a description of any situation or state of affairs. Each state may have several neighbors, so there will be a choice of how to search. We can travel down one path until we see it is a dead end, or we can consider lots of different paths at the same time, expanding each path step by step.