Artificial Intelligence: Search

At the core we are simply solving problems. The problem might be simple but being simplistic does not equate to easy. Artificial Intelligence and machine learning use several techniques to help us understand better ways to solve these problems. 

The first one being SEARCH…

When work is over and we open our home navigation, these days we might be presented with some options, eco-friendly vs fastest route, or in some instances where we travel further distances, tolls vs no-tolls. These options are “somehow” selected by “some” search process determined by thought and reasoning. But how does this even happen? 

Typically, search problems involve an agent (an entity that perceives and will act within their environment) given an initial state and a goal state, and it returns a solution of how to get from the former to the latter. 

So in this example the agent might be a representation of a car. The car needs to make decisions in order to arrive safely in its garage. 

A way to manage these decisions would be in the order of state. State is the configuration of the agent and its perceived environment. In the navigator app, the current location would be the evolving state, while actions, or choices can be made in a state to provide feedback on where the correct action was performed or not. 

Did I make the correct turn or should I have stayed on the main road? 

In order for use to make any sense of the results we need a way to format these inputs to achieve an output. Let us create a function that will receive a state (s) and action (a), together giving us a Result(s, a). This is an example of a Transitional Model.

Given we are traveling and the current state, or geo-location (current location) is constantly updating we need to determine if the action is getting us closer to our desired location or are we moving away from the goal. The State Space, the set of all the possible states reachable from the initial state by any sequence of actions, will provide the framework where we can begin to apply specific logic. Is the problem solved? NO?! Then we continue searching… but at what cost? 

Solving Search Problems

A good rule of thumb is to start with the MVS, minimum viable solution. Does this solution work? Great! We were able to perform a function that took the state and sequence of actions to the goal state… but can it be optimized?

Fundamentally, the search processes use nodes to store data:

• A state
• Its parent node, through which the current node was generated
• The action that was applied to the state of the parent to get to the current node
• The path cost from the initial state to this node

Together they create information that makes them useful in search algorithms. However, they are simply a data-structure. They don't perform any action, they are just storage. In a situation where we can actually start to search, we can use a mechanism that manages the nodes called the frontier. It starts off with some initial state, and a list of explored items, and then repeats the following actions until a solution is reach:

Repeat
1. If the frontier is empty
- Stop... There is no solution to this problem
2. Remove a node from the frontier. Let's consider this
3. If the node contails the goal state,
- Return the solution. Stop...
Else,
- Expand the node (find all the new nodes that could be reached from this node), and add resulting nodes to the frontier.
- Add the current node to the explored set.

Which Witch is Which?

In the previous example, which node should be removed to determine at the initial stage? There are multiple ways to go about the question of which nodes should be considered first, two of which can be represented by the data structures of stack (in depth-first search) and queue (in breadth-first search).

Depth-First Search (DFS)

A depth-first search algorithm exhausts each one direction before trying another direction. In these cases, the frontier is managed as a stack data structure. The catchphrase you need to remember here is “last-in first-out.” 

Pros: “Winner Winner Chicken Dinner!” At best, this algorithm is the fastest.

Cons: At worst, this algorithm will explore every possible path before finding the solution, thus taking the longest possible time before reaching the solution.

Breadth-First Search (BFS)

A breadth-first search algorithm will follow multiple directions at the same time, taking one step in each possible direction before taking the second step in each direction. In this case, the frontier is managed as a queue data structure. The catchphrase you need to remember here is “first-in first-out.” 

Pros: This algorithm is guaranteed to find the optimal solution.

Cons: At worst, this algorithm takes the longest possible time to run.

Greedy Best-First Search

Expands the node that is the closest to the goal, as determined by a heuristic function h(n). The function estimates how close to the goal the next node is, but it can be mistaken. The efficiency of the greedy best-first algorithm depends on how good the heuristic function is. For example, in a maze, an algorithm can use a heuristic function that relies on the Manhattan distance between the possible nodes and the end of the maze.

A* Search

A* search considers not only h(n), the estimated cost from the current location to the goal, but also g(n), the cost that was accrued until the current location. The algorithm keeps track of (cost of path until now + estimated cost to the goal), and once it exceeds the estimated cost of some previous option, the algorithm will ditch the current path and go back to the previous option

For A* search to be optimal, the heuristic function, h(n), should be:

1. Admissible, or never overestimating the true cost, and
2. Consistent, which means that the estimated path cost to the goal of a new node in addition to the cost of transitioning to it from the previous node is greater or equal to the estimated path cost to the goal of the previous node. To put it in an equation form, h(n) is consistent if for every node n and successor node n’ with step cost c, h(n) ≤ h(n’) + c.

Adversarial Search

What if we were not alone in this discussion making environment? Often, Artificial Intelligence that uses adversarial search is encountered in games such as tic tac toe.

Minimax

Algorithm representing winning conditions as (-1) for one side and (+1) for the other side, trying to minimize or maximize respectively.

Representing a Tic-Tac-Toe AI:

• S₀: Initial state (in our case, an empty 3X3 board)
• Players(s): a function that, given a state s, returns which player’s turn it is (X or O).
• Actions(s): a function that, given a state s, return all the legal moves in this state (what spots are free on the board).
• Result(s, a): a function that, given a state s and action a, returns a new state. This is the board that resulted from performing the action a on state s (making a move in the game).
• Terminal(s): a function that, given a state s, checks whether this is the last step in the game, i.e. if someone won or there is a tie. Returns True if the game has ended, False otherwise.
• Utility(s): a function that, given a terminal state s, returns the utility value of the state: -1, 0, or 1.

Maximizer

The Maximizer Considers the Possible Values of Future States.

[1]: Brian Yu, David J. Malan; Harvard University CS50's Introduction to Artificial Intelligence with Python

[2]: Gareth James, Daniela Witten, Trevor Hastie, Robert Tibshirani, Jonathan Taylor; An Introduction to Statistical Learning with Applications in Python