Please enable JavaScript.

Coggle requires JavaScript to display documents.

R&A, Reasoning and Agents - Coggle Diagram

- - - - Single state
        
        observable (at least in initial state)
        
        deterministic
        
        static
        
        discrete
      - Conformant
        
        solution is a sequence
        
        agent doesn't know where it is
      - Contingency
        
        non deterministic and/or partially observable
      - Exploration
        
        unknown state space (not the same as non or partially observable) you don't even know what the states are
  - - - returns solution or failure
      - frontier is the initial state of the problem
      - if the tree is not a DAG then the function may never finish
  - - - completeness (does it always eventually find the solution if it exists)
      - time complexity
      - space complexity
      - optimality
      - (time and space complexity can be measured by: max branching factor of search tree, depth of optimum solution and max depth of search space)
    - - search earliest added node
      - good for completeness and optimality
      - bad for space (especially) and time
    - - incomplete as it fails in spaces with cycles and infinite depths (can be modified but increases space complexity
      - very bad time complexity O(b^m)
      - Good for space complexity O(bm)
      - Non optimal
    - - DFS with a certain depth limit l to prevent issues caused by infinite depths
    - - Is optimal
      - Has linear space
    - - Sometimes we have extra information about a graph which allows us to create better heuristics
      - Best-First Search
        
        This simple expands the nodes deemed best first
        
        A* Search
        
        Considers cost of path (sum of weightings of edges) instead of just the shortest numbers of nodes to the goal
        
        Time and space is exponential
        
        Greedy Best-First-Search
        
        select node which appears to be closest to the goal at each step
        
        imcomplete as it can get stuck in loops
        
        not optimal
  - - - works in deterministic, zero sum, two player, turn based games
      - player one chooses all the moves which maximise his score
      - player 2 then chooses the move which minimises the score (the score is measured from player 1's perspective)
      - Gives the best achievable score given perfect play by player1
      - all the nodes in the game tree are given a score.
      - For any non simple game it isn't feasible to calculate exactly as the tree is so large
      - is a bottom up evaluation. It recurses over the whole tree
    - - applicable when min max is
      - this is used when the game tree is too big for minmax algorithm. it doesn't bother evaluating irrelevant branches
      - a-b pruning works by using a top down version of minmax.. This allows it to prune branches which are irrelevant (as they aren't max or min).
      - a is best max value
      - b is best min value
      - like minmax it is optimal
      - with perfect good move ordering it allows us to explore twice the depth in the same time.
      - there are many heuristics to allow for accurate estimations such as cut-off and quiescence search
- - - - Model based Agent: an agent which can handle partially known environments by using a model. This requires it to have its own history plus information about unperceivable aspects of the world to build its model.
        
        has state (memory)
        
        has unperceived aspects of the world (model). This is information about how the world works. this allows us to deduce facts about future states given the current state
      - Goal based Agent: has variable goals and forms plans to reach those goals. These goals can't be conflicting
      - Utility based Agent: has multiple (possibly) conflicting goals. Chooses action based on what optimises utility. Allows us to balance multiple conflicting roles when combined with probabilities using expected utility. Uses a utility function to quantify performance measure. don't be tempted to make utility function then use that as the performance measure
      - Single reflex agent: Actions depend on immediate precepts. This means they only work for problems if the correct decision can be made with only the current inputs
        
        usually requires environment to be fully observable
        
        infinite loops are unavoidable in partially observable environments. can randomise action to help mitigate this
    - - edge triggered: sensor triggers once on a stimuli condition
      - level triggered: continuous whilst a stimuli is at a certain level
  - - - Deterministic vs Stochastic
        
        Stochastic environment: given an certain state and an action the next state can only be described with probabilities. There is an element of randomness.
        
        Deterministic environment: the next state is fully determined by current state and the action performed. This has no randomness and is opposite to a stochastic environment
      - Episodic vs Sequential
        
        Sequential Environment: next action depends on the last action
        
        Episodic Environment: Next action doesn't depend on the last action.
      - Dynamic vs Static
        
        Dynamic environment: environment changes as the agent decides. i.e. self driving car
        
        Static Environment: environment stays unchanged whilst the agent decides. i.e. chess
      - Discrete vs Continuous
        
        Continuous Environment: percepts, actions and episodes are continuous. i.e. self driving car
        
        Discrete Environment: percepts, actions and episodes are discrete i.e. chess
      - Multi agent vs Single agent
        
        Multi Agent Environment: multiple entities can be modelled as agents
        
        Single Agent Environment: only one agent
      - Fully observable vs Partially observable
        
        Fully observable: when the entire state of the system can be described by the agents sensors
        
        Partially observable environment: an agents sensors can't fully describe the state of the system