MIT807 Lecture 2: Artificial Intelligence PDF

LECTURE 2 MIT807 ARTIFICIAL INTELLIGENCE & ITS BUSINESS APPLICATIONS Dr. Babatunde Sawyerr Department of Computer Sciences  Uninformed Search  Uninformed search, also called blind search and naïve search,  It is a class of general-purpose search algorithms...

LECTURE 2 MIT807 ARTIFICIAL INTELLIGENCE & ITS BUSINESS APPLICATIONS Dr. Babatunde Sawyerr Department of Computer Sciences  Uninformed Search  Uninformed search, also called blind search and naïve search,  It is a class of general-purpose search algorithms that operate in a brute force way.  These algorithms can be applied to a variety of search problems, but since they don’t take into account the target problem, they are inefficient.  SEARCH AND AI  Search is an important aspect of AI because in many ways, problem solving in AI is fundamentally a search.  Search is a key computational mechanism in many AI agents.  Search can be defined as a problem-solving technique that enumerates a problem space from an initial position in search of a goal position (or solution).  The manner in which the problem space is searched is defined by the search algorithm or strategy.  Search strategies offer different ways to enumerate the search space.  How well a strategy works is based on the problem at hand.  General State Space Search What is a search space? When solving a problem, it’s convenient to think about the solution space in terms of a number of actions that we can take, and the new state of the environment as we perform those actions. As we take one of multiple possible actions (each have their own cost), our environment changes and opens up alternatives for new actions. The problem of search is to find a sequence of operators that transition from the start to goal state. That sequence of operators is the solution.  Search in a Physical Space Let’s consider a simple search problem in physical space Search in a Physical Space  Search in Puzzle Space The “Towers of Hanoi” puzzle is an interesting example of a state space for solving a puzzle problem. The object of this puzzle is to move a number of disks from one peg to another (one at a time), with a number of constraints that must be met. Each disk is of a unique size and it’s not legal for a larger disk to sit on top of a smaller disk. The initial state of the puzzle is such that all disks begin on one peg in increasing size order. Our goal (the solution) is to move all disks to the last peg. Search in Puzzle Space  Trees, Graphs, And Representation  A graph is a finite set of vertices (or nodes) that are connected by edges (or arcs).  A loop (or cycle) may exist in a graph, where an arc (or edge) may lead back to the original node.  Graphs may be undirected where arcs do not imply a direction, or they may be directed (called a digraph) where a direction is implicit in the arc.  An arc can also carry a weight, where a cost can be associated with a path.  Each of these graphs also demonstrates the property of connectivity.  Trees, Graphs, And Representation  Both graphs are connected because every pair of nodes is connected by a path. If every node is connected to every node by an arc, the graph is complete.  One special connected graph is called a tree, but it must contain no cycles.  Building a representation of a graph is simple and one of the most common representations is the adjacency matrix. Trees, Graphs, And Representation Trees, Graphs, And Representation Trees, Graphs, And Representation Trees, Graphs, And Representation Trees, Graphs, And Representation Common orders of search functions  O-Notation Order  O(1) Constant (regardless of the number of nodes).  O(n) Linear (consistent with the number of nodes)  O(log n) Logarithmic  O(n2) Quadratic  O(cn) Geometric  O(n!) Combinatorial Common orders of search functions  Big-O notation provides a worst-case measure of the complexity of a search algorithm and is a common comparison tool for algorithms.  We’ll compare the search algorithms using space complexity (measure of the memory required during the search) and time complexity (worst-case time required to find a solution).  General Search Paradigms  Generate and Test  Generate a potential solution and then check it against the solution. If the solution is found then stop, otherwise, repeat by trying another potential solution.  Random Search A solution is randomly selected from the current state (by selecting a given valid operator and applying it). If the goal state is reached, then stop, otherwise another solution is randomly selected  These methods are blind methods of search.  Depth-First Search (DFS)  DFS algorithm is a technique for searching a graph that begins at the root node, and exhaustively searches each branch to its greatest depth before backtracking to previously unexplored branches. Nodes found but yet to be reviewed are stored in a LIFO queue (also known as a stack).  Space complexity for DFS is O(bd)  Time complexity is geometric (O(bd)) Depth-First Search (DFS) An Example State Space Problem  Depth-Limited Search (DLS)  DLS is a modification of depth-first search that minimizes the depth that the search algorithm may go. In addition to starting with a root and goal node, a depth is provided that the algorithm will not descend below.  Any nodes below that depth are omitted from the search.  This modification keeps the algorithm from indefinitely cycling by halting the search after the pre-imposed depth. Depth-Limited Search (DLS)  Iterative Deepening Search (IDS)  IDS is a derivative of DLS and combines the features of depth- first search with that of breadth-first search.  IDS operates by performing DLS searches with increased depths until the goal is found.  The depth begins at one, and increases until the goal is found, or no further nodes can be enumerated.  By minimizing the depth of the search, the algorithm is forced to also search the breadth of the graph.  If the goal is not found, the depth that the algorithm is permitted to search is increased and the algorithm is started again.  IDS is advantageous because it’s not susceptible to cycles (a characteristic of DLS, upon which it’s based). It also finds the goal nearest to the root node.  Iterative Deepening Search (IDS)  Unlike DFS and DLS, IDS is will always find the best solution and therefore, it is both complete and optimal.  Breadth-First Search (BFS)  In BFS, the graph is searched from the root node in order of the distance from the root.  BFS is guaranteed to find the best possible solution (shallowest) in a non-weighted graph, because the order of the search is nearest the root.  Rather than digging deep down into the graph, progressing further and further from the root (as is the case with DFS), BFS checks each node nearest the root before descending to the next level.  The implementation of BFS uses a FIFO (first-in-first-out) queue.  Breadth-First Search (BFS)  As new nodes are found to be searched, these nodes are checked against the goal, and if the goal is not found, the new nodes are added to the queue.  To continue the search, the oldest node is dequeued (FIFO order).  The disadvantage of BFS is that each node that is searched is required to be stored (space complexity is O(bd)). The entire depth of the tree does not have to be searched, so d in this context is the depth of the solution, and not the maximum depth of the tree.  Time complexity is also O(bd). Breath-First Search (BFS)  Bidirectional Search  The Bidirectional Search algorithm is a derivative of BFS that operates by performing two breadth-first searches simultaneously, one beginning from the root node and the other from the goal node.  When the two searches meet in the middle, a path can be reconstructed from the root to the goal. The meeting of searches is determined when a common node is found.  Bidirectional search is an interesting idea, but requires that the goal is known in the graph. This isn’t always practical, which limits the application of the algorithm.  Bidirectional Search  The time and space complexity for bidirectional search is O(bd/2), since we’re only required to search half of the depth of the tree. Since it is based on BFS, bidirectional search is both complete and optimal.  Uniform-Cost Search (UCS)  Uniform-cost search is an uninformed search method because no heuristic is actually used. The algorithm measures the actual cost of the path without attempting to estimate it.  The algorithm for UCS uses the accumulated path cost and a priority queue to determine the path to evaluate Uniform-Cost Search (UCS) Uniform-Cost Search (UCS)  Algorithm Advantages Each of the algorithms has advantages and disadvantages based on the graph to be searched.  if the branching factor of the graph is small, then BFS is the best choice.  If the tree is deep, but a solution is known to be shallow in the graph, then IDS is a good choice.  If the graph is weighted, then UCS should be used as it will always find the best solution where DFS and BFS will not. Algorithms Summary