Chapter 3 Sections 1 - 5 1 Solving Problems by Searching Reflex agent is simple base their actions on a direct mapping( ) from states to actions but cannot work well in environments which

this mapping would be too large to store and would take too long to learn Hence, goal-based agent is used 2 Problem-solving agent Problem-solving agent A kind of goal-based agent It solves problem by finding sequences of actions that lead to

desirable states (goals) To solve a problem, the first step is the goal formulation, based on the current situation 3 Goal formulation The goal is formulated as

a set of world states, in which the goal is satisfied Reaching from initial state goal state Actions are required Actions are the operators causing transitions between world states Actions should be abstract enough at a certain degree, instead of very detailed

E.g., turn left VS turn left 30 degree, degree etc. 4 Problem formulation The process of deciding what actions and states to consider E.g., driving zolfi Riyadh in-between states and actions defined

States: Some places in Zolfi & Riyadh Actions: Turn left, Turn right, go straight, accelerate & brake, etc. 5 Search Because there are many ways to achieve the same goal Those ways are together expressed as a tree Multiple options of unknown value at a point, the agent can examine different possible

sequences of actions, and choose the best This process of looking for the best sequence is called search The best sequence is then a list of actions, called solution 6 Search algorithm Defined as taking a problem

and returns a solution Once a solution is found the agent follows the solution and carries out the list of actions execution phase Design of an agent Formulate, search, execute 7

8 Environments for PS agent Environment is: static formulating and solving the problem is done without paying attention to any changes that might occur in the environment observable the agent knows its initial state

discrete a finite number of actions can be defined 9 Environments for PS agent deterministic solutions are just single action sequences effect of all actions are known no percepts are needed except the first percept so called open-loop

From these, we know that problem-solving agent is the easiest one 10 Well-defined problems and solutions A problem is defined by 4 components: Initial state Successor functions: state

space. Path. Goal Test. Path Cost. 11 Well-defined problems and solutions A problem is defined by 4 components: The initial state that

the agent starts in The set of possible actions (successor functions) These two items define the state space the A set of all states reachable from the initial state path in the state space:

any sequence of actions leading from one state to another 12 Well-defined problems and solutions The goal test Applied if to the current state to test the agent is in its goal

Sometimes the goal is described by the properties instead of stating explicitly the set of states Example: Chess the

agent wins if it can capture the KING of the opponent on next move no matter what the opponent does 13 Well-defined problems and solutions A path cost function, assigns a numeric cost to each path = performance measure denoted by g to distinguish the best path from others

Usually the path cost is the sum of the step costs of the individual actions (in the action list) 14 Well-defined problems and solutions Together a problem is defined by Initial state Successor function Goal test Path cost function

The solution of a problem is then a path from the initial state to a state satisfying the goal test Optimal solution the solution with lowest path cost among all solutions 15 Formulating problems Besides the four components for problem formulation

anything else? Abstraction the process to take out the irrelevant() information leave the most essential parts to the description of the states Conclusion: Only the most important parts that are contributing to searching are used 16

Example 17 From our Example 1. Formulate Goal - Be In Amman 2. Formulate Problem - States : Cities - actions : Drive Between Cities 3. Find Solution - Sequence of Cities : ajlun Jarash - Amman 18

Our Example 1. Problem : To Go from Ajlun to Amman 2. Initial State : Ajlun 3. Operator : Go from One City To another . 4. State Space : {Jarash , Salt , irbed}.. 5. Goal Test : are the agent in Amman. 6. Path Cost Function : Get The Cost From The Map. 7. Solution : { {Aj Ja Ir Ma Za Am} , {Aj Ir Ma Za Am} . {Aj Ja Am} }

8. State Set Space : {Ajlun Jarash Amman} 19 Single-state problem formulation A problem is defined by four items: 1. 2. initial state e.g., "at Arad" actions or successor function S(x) = set of actionstate pairs 3. e.g., S(Arad) = {, }

goal test, can be explicit, e.g., x = "at Bucharest" implicit, e.g., Checkmate(x) 20 Single-state problem formulation 5. path cost (additive)

e.g., sum of distances, number of actions executed, etc. c(x,a,y) is the step cost, assumed to be 0 A solution is a sequence of actions leading from the initial state to a goal state 21 Example problems Toy problems those

intended to illustrate or exercise various problem-solving methods E.g., puzzle, chess, etc. Real-world problems tend to be more difficult and whose solutions people actually care about E.g., Design, planning, etc. 22 Toy problems Example: vacuum world Number of states: 8

Initial state: Any Number of actions: 4 left, right, suck, noOp Goal: clean up all dirt Goal states: {7, 8} Path Cost: Each step costs 1 23 24 The 8-puzzle 25

The 8-puzzle States: a state description specifies the location of each of the eight tiles and blank in one of the nine squares Initial State: Any state in state space Successor function:

the blank moves Left, Right, Up, or Down Goal test: current state matches the goal configuration Path cost: each step costs 1, so the path cost is just the length of the path 26

The 8-queens There are two ways to formulate the problem All of them have the common followings: Goal test: 8 queens on board, not attacking to each other Path cost: zero 27 The 8-queens (1) Incremental formulation

involves operators that augment the state description starting from an empty state Each action adds a queen to the state States: any arrangement of 0 to 8 queens on board Successor add function:

a queen to any empty square 28 The 8-queens (2) Complete-state formulation starts with all 8 queens on the board move the queens individually around States: any arrangement of 8 queens, one per column in the leftmost columns

Operators: move an attacked queen to a row, not attacked by any other 29 The 8-queens Conclusion: the right formulation makes a big difference to the size of the search space 30

Example: robotic assembly states?: real-valued coordinates of robot joint angles parts of the object to be assembled actions?: continuous motions of robot joints goal test?: complete assembly path cost?: time to execute 31 3.3 Searching for solutions Finding out a solution is done by searching through the state space

All problems are transformed as a search tree generated by the initial state and successor function 32 Initial state Search tree The

root of the search tree is a search node() Expanding() applying successor function to the current state Thereby( )generating a new set of states leaf nodes the states having no successors or they havent yet been expanded (fringe:)

Refer to next figure 33 Tree search example 34 Tree search example 35 Search tree The essence( )of searching in

case the first choice is not correct choosing one option and keep others for later inspection Hence we have the search strategy which determines the choice of which state to expand good choice fewer work faster Important: state

space search tree 36 Search tree State space has unique states {A, B} while a search tree may have cyclic paths: A-B-A-B-A-B- A good search strategy should avoid such paths 37

Search tree A node is having five components STATE: which state it is in the state space PARENT-NODE: from which node it is generated ACTION: which action applied to its parent-node to generate it PATH-COST: the cost, g(n), from initial state to the node n itself DEPTH: number of steps along the path from the initial state 38

39 Search tree In order to better organize the fringe we use a queue to store them (FIFO) Operations on a queue MAKE-QUEUE(element, ) EMPTY?(queue) FIRST(queue) REMOVE-FIRST(queue)

INSERT(element, queue) INSERT-ALL(elements, queue) 40 Measuring problem-solving performance The evaluation of a search strategy Completeness: is the strategy guaranteed to find a solution when there is one? Optimality:

does the strategy find the highest-quality solution when there are several different solutions? Time complexity: how long does it take to find a solution? Space how

complexity: much memory is needed to perform the search? 41 Measuring problem-solving performance In AI, complexity is expressed in b, branching factor, maximum number of successors of any node d, the depth of the shallowest( )goal node m, the maximum length of any path in the state

space Time and Space is measured in number of nodes generated during the search maximum number of nodes stored in memory 42 Measuring problem-solving performance For effectiveness of a search algorithm we can just consider the total cost The total cost = path cost (g) + search cost

search cost = time necessary to find the solution Trade-off: (long time, optimal solution with least g) vs. (shorter time, solution with slightly lager path cost g) 43 3.4 Uninformed search strategies Uninformed search no

information about the number of steps or the path cost from the current state to the goal search the state space blindly( ) Informed search, or heuristic search a cleverer strategy that searches toward the goal, based on the information from the current state so far 44

Uninformed search strategies Breadth()-first search Uniform cost search Depth()-first search Depth-limited search Iterative deepening search Bidirectional search 45

Breadth-first search The root node is expanded first (FIFO) All the nodes generated by the root node are then expanded And then their successors and so on 46 Breadth-first search (Analysis) Breadth-first search Complete find the solution eventually Optimal, if the path cost is a non-decreasing

function of the depth of the node The disadvantage if the branching factor of a node is large, for even small instances (e.g., chess) the space complexity and the time complexity are enormous 47 Breadth-first search (Analysis) assuming 10000 nodes can be processed per second, each

with 1000 bytes of storage 48 Uniform cost search Breadth-first finds the shallowest goal state but not necessarily be the least-cost solution work only if all step costs are equal Uniform cost search modifies by

breadth-first strategy always expanding the lowest-cost node The lowest-cost node is measured by the path cost g(n) 49 Uniform cost search the first found solution is guaranteed to be the cheapest least in depth But restrict to non-decreasing path cost Unsuitable for operators with negative cost

50 Depth-first search Always expands one of the nodes at the deepest level of the tree Only when the search hits a dead end goes back and expands nodes at shallower levels Dead end leaf nodes but not the goal Backtracking( )search only one successor is generated on expansion rather than all successors fewer memory

51 Depth-first search Expand deepest unexpanded node Implementation: fringe = LIFO queue, i.e., put successors at front 52

Depth-first search Expand deepest unexpanded node Implementation: fringe = LIFO queue, i.e., put successors at front 53 Depth-first search Expand deepest unexpanded node Implementation:

fringe = LIFO queue, i.e., put successors at front 54 Depth-first search Expand deepest unexpanded node Implementation: fringe = LIFO queue, i.e., put successors at front

55 Depth-first search Expand deepest unexpanded node Implementation: fringe = LIFO queue, i.e., put successors at front 56

Depth-first search Expand deepest unexpanded node Implementation: fringe = LIFO queue, i.e., put successors at front 57 Depth-first search Expand deepest unexpanded node Implementation:

fringe = LIFO queue, i.e., put successors at front 58 Depth-first search Expand deepest unexpanded node Implementation: fringe = LIFO queue, i.e., put successors at front

59 Depth-first search Expand deepest unexpanded node Implementation: fringe = LIFO queue, i.e., put successors at front 60 Depth-first search

Expand deepest unexpanded node Implementation: fringe = LIFO queue, i.e., put successors at front 61 Depth-first search Expand deepest unexpanded node Implementation:

fringe = LIFO queue, i.e., put successors at front 62 Depth-first search Expand deepest unexpanded node Implementation: fringe = LIFO queue, i.e., put successors at front

63 Depth-first search 64 Depth-first search (Analysis) Not complete because a path may be infinite or looping then the path will never fail and go back try another option Not optimal

it doesn't guarantee the best solution It overcomes the time and space complexities 65 Depth-limited search It is depth-first search with a predefined maximum depth

However, it is usually not easy to define the suitable maximum depth too small no solution can be found too large the same problems are suffered from Anyway the search is complete but still not optimal 66 Iterative deepening search (IDS)

No choosing of the best depth limit It tries all possible depth limits: first 0, then 1, 2, and so on combines the benefits of depth-first and breadth-first search 67 Iterative deepening search 68 Iterative deepening search

(Analysis) optimal complete Time and space complexities reasonable suitable for the problem having a large search space and the depth of the solution is not known 69 Iterative lengthening search (ILS)

IDS is using depth as limit ILS is using path cost as limit an iterative version for uniform cost search has the advantages of uniform cost search while but avoiding its memory requirements ILS incurs substantial overhead compared

to uniform cost search 70 Bidirectional search Run two simultaneous searches one forward from the initial state another backward from the goal stop when the two searches meet However, computing backward is difficult A

huge amount of goal states at the goal state, which actions are used to compute it? can the actions be reversible to computer its predecessors? 71 72 Comparing search strategies 73 Avoiding repeated states

for all search strategies There is possibility of expanding states that have already been encountered and expanded before, on some other path may cause the path to be infinite loop forever Algorithms that forget their history are

doomed () to repeat it 74 Avoiding repeated states Three ways to deal with this possibility Do not return to the state it just came from Refuse generation of any successor same as its parent state

Do not create paths with cycles Refuse generation of any successor same as its ancestor states Do not generate any generated state Not

only its ancestor states, but also all other expanded states have to be checked against 75 Avoiding repeated states We then define a data structure closed list a set storing every expanded node so far If the current node matches a node on the closed list, discard it. 76

Searching with Partial Information What happens when knowledge of the states or actions is incomplete? This leads to 3 distinct problem types Sensorless or conformant problems Contingency problems Exploration problems 77 Sensorless(captor) problems The agent has no sensors

could be in one of several possible initial states each action lead to one of several possible successor states each of these successor states is called belief state current belief about the possible physical states 78 79

Contingency( )problems The environment such that the agent can obtain new information from its sensors after acting Then the effect of actions are uncertain Hence build a tree to represent the different possible effects of an action the contingencies Hence the agent is interleaving search, execute, search, execute, rather than single search, execute

80 Exploration problems The states and actions about the environment are unknown It has to experiment To perform the actions and see its results It involves significant danger because it may cause the agent really damaged If it survives, it learns the environment and the effects about its actions,

which it can use to solve subsequent problems 81