Pathfinding Techniques Quiz

Goal-based Agents

• Reflex agents map states to actions.
• Goal-based agents use problem-solving or planning.
• Goal-based agents work towards defined goals.
• Agents consider the impact of actions on future states.
• The agent's job is to find the actions or series of actions which achieve the goal.
• Agents can be formalized as a search through possible solutions.
• Examples include mazes and the 8-queen problem.

Problem Solving as Search

• Solving a problem involves defining a problem and then searching for a solution.
• The problem definition includes goal formulation and problem formulation.
• Search is a two-stage process including:
  • Mental or offline exploration of possibilities.
  • Executing the found solution.

Problem Formulation

• Initial state: The starting point of the agent.
• States: All states reachable from the initial state.
• Actions: Available actions at a state.
• Transition model: Describes what each action does.
• Goal test: Checks if a given state is a goal state.
• Path cost: Assigns a numeric cost to a path based on performance measures.

Examples

• The 8-queen problem involves placing 8 queens on a chessboard without any attacking each other.
• Finding a path in Romania involves determining the shortest route to Bucharest.
• 8-puzzle involves sliding numbered tiles to reach a target configuration.
• Finding a solution to a Maze.

Search Problems

• A search problem includes:
  • A state space.
  • A successor function (actions, costs).
  • A start state.
  • A goal test.
  • A solution that's a sequence of actions that transforms the start state to a goal state

Search Problems are Models

• Search problems provide a way to represent problem configurations.
• This allows for an agent to determine how to solve a problem.

State Space Graphs and Search Trees

• A state space graph shows all possible world configurations.
• Arcs represent successor actions.
• A goal test is a set of goal nodes (maybe only one).
• State space graphs are mathematically useful, though often impractical to generate entirely.
• Search trees represent plans and outcomes of possible decisions.

Search Example: Romania

• The states are cities in Romania.
• The successor function is based on paths between cities with costs.

Searching with a Search Tree

• The search involves expanding out potential plans.
• The search maintains a fringe of partial plans to consider.
• The goal is to expand as few tree nodes as possible.

General Tree Search

• The function TREE-SEARCH returns a solution or failure.
• It initializes the search tree from an initial state.
• It loops until either a solution is found or no more candidates are left.
• The solution is returned if a goal state is found.

Agent, State, Actions, Transition Model, Result, State Space, Goal Test, Path Cost

• Agent: An entity that perceives its environment and acts upon it.
• State: A configuration of the agent and its environment.
• Actions: Choices that can be made in a state.
• Transition Model: Describes the result of applying applicable actions to a given state.
• Result(s, a): Returns the state resulting from an action in a state.
• State Space: The set of all states reachable from the initial state.
• Goal Test: Determines if a state is a goal state.
• Path Cost: A numeric cost associated with a given path.

Revised Approach

• Start with the initial state as a frontier
• Start with an empty explored set
• Loop through until empty frontier occurs
• Remove the node from the frontier
• If goal state, return solution
• Add the node to the explored set
• Expand the node, resulting nodes go to the frontier if they aren't already in the frontier or explored set.

Example: 8-Queens, 8-Puzzle, Route-finding

The problem formulations were provided for these problems previously.