Problem-Solving Agents and Search Algorithms

• Problem-solving involves finding a sequence of actions that achieve a desired goal.
• Searching is a common problem-solving technique.

Problem-Solving Agents

• A problem-solving agent decides what actions and states to consider to reach the goal.
• Goal formulation is the first step, organizing the steps needed to achieve the goal.
• Problem formulation then decides what actions and states to consider, given the goal.
• Searching involves examining possible sequences of actions to find a path to the goal.
• Execution involves carrying out the recommended actions.
• The "formulate, search, execute" design implements a goal-based agent.

Well-Defined Problems and Solutions

• A problem is defined by five components: initial state, actions, transition model, goal test, and path cost.
• The initial state is where the agent starts.
• Actions are descriptions of possible actions available to the agent.
• The transition model describes what each action does.
• The goal test determines if a given state is a goal state.
• The path cost assigns a numeric cost to each path.
• A solution is a sequence of actions that leads from the initial state to a goal state.
• Optimal solution has the lowest path cost among all solutions.
• Real-world problems can be complex, requiring abstraction to formulate them at a solvable level.

Example Problems : Toy Problems

• Used to illustrate or exercise different problem-solving methods.
• The vacuum world has a discrete, finite set of states.
• States in the vacuum world can be squares with or without dirt, and the agent location.
• Actions in the vacuum world can be left, right, or suck.
• The goal is for all squares to be clean.
• The path cost is usually the number of actions taken.
• The 8-puzzle consists of a 3x3 board with 8 numbered tiles and a blank space.
• States in the 8-puzzle can be defined by the location of each of the tiles.
• Actions in the 8-puzzle can be moving the blank space left, right, up, or down.
• The goal is to reach a specified configuration.
• The path cost is the number of moves.
• The 8-queens problem is to place eight queens on a chessboard so that no queen attacks any other.
• States in the 8-queens problem can be any arrangement of 0 to 8 queens on the board.
• Actions in the 8-queens problem can be to add a queen to any empty square.
• The goal is to have 8 queens on the board, none of which attack each other.

Example Problems : Real-World Problems

• These are problems that people actually care about solving.
• Route-finding problems involve finding the best route between two locations.
• States in route-finding problems can be locations.
• Actions in route-finding problems can be to move from one location to another.
• The goal is to reach the destination.
• The path cost can be distance, time, or money.
• Touring problems involve finding a route that visits each location exactly once.
• States in touring problems can be partial tours.
• Actions in touring problems can be to visit the next location.
• The goal is to complete a tour that visits all locations.
• The path cost can be distance, time, or money.
• Traveling Salesperson Problem (TSP) is a touring problem where each city must be visited exactly once.
• VLSI layout problems involve placing components on a chip to minimize area and wire length.
• Robot navigation involves moving a robot from one location to another while avoiding obstacles.
• Automatic assembly sequencing involves finding the order in which to assemble the parts of a product.
• Internet searching involves finding relevant web pages.

Searching for Solutions

• Search algorithms explore the state space to find a solution.
• Search algorithms are judged on completeness, optimality, time complexity, and space complexity.
• Completeness means the algorithm is guaranteed to find a solution if one exists.
• Optimality means the algorithm finds the best solution.
• Time complexity is the amount of time the algorithm takes to find a solution.
• Space complexity is the amount of memory the algorithm needs to find a solution.
• Uninformed search algorithms have no additional information about the state or search space other than that provided in the problem definition.
• Informed search algorithms use problem-specific knowledge to guide the search.