AI Search Problems Overview

-

What is an agent?


agent - an entity that perceives and acts

planning agent - an agent that make decisions based on (hypothesized) consequences of actions
  • Planning agents simulate situations and performs/executes the best action according to its simulations done in the "planning" stage
    • Planning agents consider how the world would be
  • Planning agents must have a model of how the world evolves in response to actions
  • Planning agents must formulate a goal (test)
  • Planning agents are complete (i.e. they never get stuck and always find a solution, since the plan ahead)
  • The agent does not actually perform all the plans out in the real world
  • The planning is all done "in simulation"

search agent - a planning agents that solves search problems


Search problems


search problem - a type of planning problem with the four components (listed below); the environment in which a rational planning agent exists in
  • Search operates over models of the real world

Components of a search problem

  1. state space - the set of all possible states that are possible in your given world (composed of the world state and search state)
    • states - abstracted representations/configurations of the world; abstractions/representations of the world
      • One difference in detail gives a completely new/another state
      • Types of states
        • world states - states that include every last detail of the environment
        • search states - states that keep only the details needed for planning (abstracted states)
      • The features/components of a state (the minimum state space) must each help uniquely determine/define the state but still be valuable enough to help solve the search 
      • The state space has a large set of world states and a smaller set of search states
      • The state space has a lot of world states (has a large set of world states), because world states include every detail
      • The state space has fewer (but still a lot of) search states, because search states are less detailed than world states
  2. transition/successor function, T(s,a,s') - a function that, given a state, returns the adjacent/next states that can be reached from the given/current state (and the cost of the transition)
    • A successor function is a function that takes in a state "s" and an action "a" and computes the cost of performing that action "a" as well as the successor state "s' "
    • successor state, s' - the state the world would be in if the given agent performed that action "a" from state "s"
  3. Actions and their costs
  4. Start and goal states
    • start state - the state in which an agent exists initially
    • goal test - a function that takes a state as input and determines whether it is a goal state (outputs yes or no)
    • goal state - a state that passes the goal test
      • There can be multiple goal states

Solution to a search problem

plan - the solution to a search problem; a sequence of actions which transforms the start state to a goal state
  • How to make a plan
    1. Consider the start state
    2. Explore the state space using the successor function, iteratively computing successors of various states until the agent has arrived at a goal state, at which the path from the start to goal state will have been determined

strategy - the order in which states are considered (the order in which states are expanded/popped out from the fringe of the search tree or state space graph)


Types of search problems (summary chart)


Comments

Post a Comment

Popular posts from this blog

Where C Variables are Stored in Memory

-
Image
Memory sections stack - the portion of memory that stores variables that were declared inside functions (i.e. stores local variables and constants) local variables are freed when the function returns (these variables cannot be accessed once the function ends) Stack memory grows downward heap - the portion of memory that stores things that were created by malloc() Data on the heap persists across functions (unlike the local variables of stack memory) Heap memory grows upward static - the portion of memory that stores "pre-allocated" variables including static and global variables (variables declared outside functions), constants, and string literals  Two sections of static memory:  read-only (stores variables that can only be read and not modified) read-write (stores variables that can be both read and written to (modified)) Static memory does not grow or shrink code (text) - the portion of memory that stores the executable instructions and constants C...
Read more

Layers of Representation of Machine Structures

-
Image
Layers of representation (high to low level) High-level language program  high-level language - a programming language that uses English and mathematical symbols in its instructions (e.g. C)  High-level programming languages are abstractions to lower-level programming languages  compiler - turns high-level language problem into an assembly language program Assembly language program  assembly language - a low-level programming language for a computer in which there is a strong correspondence between the language and the architecture's machine code instructions (e.g. MIPS, x86, 32b ARM)  Assembly languages are abstractions of machine languages  Assembly code is human-readable version of computer's native machine code  There are different assembly languages for different CPUs following different ISAs (each assembly language is tied to a particular ISA)  assembler - turns assembly language program into machine language program ...
Read more

Constraint Satisfaction Problems

-
Image
identification problem  - a problem in which the agent must identify whether it is a goal state or not, with no regards of how it arrives at that goal In identification problems, the goal itself it important, not the path of reaching the goal All paths have the same depth, which is the number of variables in the problem constraint satisfaction problem (CSP)  - an identification search problem in which each state must satisfy a number of constraints (limitations) in order to be a valid goal state In CSPs, states are partial assignments  of variables (i.e. some variables have been assigned values while others have not) constraint graph  - a graph whose nodes represent a CSP's variables and edges represent the constraints between the variables/nodes Components of a CSP variables - a set of $N$ variables ($X_1,...,X_N$) that can each take on a single value from the domain domain  - a set ${x_1,...,x_d}$ representing all possible values that a ...
Read more