Intelligent Agents, Best-First, and Breadth-First Search

Posted on Feb 5, 2025 in Computers

Intelligent Agents

An intelligent agent is an entity capable of perceiving its environment, processing these perceptions, and responding or acting rationally. This means acting correctly and in a way that maximizes an expected result. Agents operate within an environment. There are several environment types:

  • Accessible vs. Inaccessible: In an accessible environment, sensors provide all relevant information.
  • Deterministic vs. Non-Deterministic: For a given deterministic environment, the next state can be obtained from the current state and the agent’s actions.
  • Episodic vs. Non-Episodic: Episodic environments are simpler because the agent does not have to think ahead.
  • Discrete vs. Continuous: A discrete environment has a number of concrete, clearly defined actions. Chess is discrete because there is a fixed number of movements on every play.
  • Static vs. Dynamic: A dynamic environment may change while the agent is reasoning. In a static environment, the agent does not have to worry about the passage of time.

Best-First Search

In Best-First search, if the node that receives the best assessment is expanded first, then we are making a ‘best-first’ approach. Rather than expanding the absolute ‘best’ node, it expands the one that *seems* to be the best according to our evaluation function. This takes into account all nodes that have been seen so far. Using the cumulative cost (as in uniform cost search) does not necessarily guide the search towards the goal. For this, an estimate of the cost of the path from the current state to a goal (h(n)) is used. This strategy (minimizing the estimated cost to achieve a goal) is sometimes called a greedy strategy. The evaluation function (h) can be anything, as long as h(n) = 0 if n is a goal. A greedy strategy is susceptible to errors. The time complexity in the worst case is O(bm), where m is the maximum depth of the search space.

Breadth-First Search

Breadth-First Search (BFS) is a graph search algorithm that starts at the root node and explores all the neighboring nodes. Then, for each of those nearest nodes, it explores their unexplored neighboring nodes, and so on, until it finds the target. It works exhaustively. This search traverses the entire graph or sequence without considering the objective until it finds it. It does not use a heuristic.

In terms of the algorithm, all child nodes obtained by expanding a node are added to a FIFO (First-In, First-Out) queue. In typical implementations, nodes that have not yet had their neighbors examined are placed in a container (like a queue or linked list) called “open,” and then once examined, they are placed in the container “closed.”

Algorithm:

  1. Put the root node in the queue.
  2. Take a node out of the queue and examine it:
    • If the desired element is found in this node, stop the search and return a result.
    • Otherwise, queue any successors (direct child nodes) that have not yet been examined.
  3. If the queue is empty, every node on the graph has been considered – stop the search and return “not found.”
  4. Repeat Step 2.

Procedure:

  • Given a source vertex s, Breadth-First Search systematically explores the vertices of G to “discover” all vertices reachable from s.
  • It calculates the distance (smallest number of vertices) from s to all reachable vertices.
  • BFS produces a tree that contains all reachable vertices.
  • The path from s to each vertex in this tree contains the minimum number of vertices. It is the shortest path, measured in the number of vertices.
  • Its name is due to uniformly expanding the frontier between discovered and undiscovered nodes. It reaches nodes k distance away only after reaching all nodes at a distance of k-1.