Please enable JavaScript.

Coggle requires JavaScript to display documents.

AI Week 7, Typically, AI problems have a large number of states so its…

- - - - •Observable, i.e., the agent knows the current state
      - •Discrete, i.e., there are only finitely many actions at any state
      - •Known, i.e., the agent knows which states are reached by each action
      - •Deterministic, i.e., each action has exactly one outcome
- - - - We expand the shallowest unexpanded node, FIFO; the root node is expanded first before all the successors of the root and then the the next level and so forth until we add a goal node to the frontier - DON'T ADD CHILDREN TO THE FRONTIER IF ALREADY THERE OR IN THE LIST OF ALREADY VISITED NODES
        
        COMPLETE - it will find the goal node if its at some finite depth
        
        OPTIMAL - if the path cost is a non-decreasing function of the depth of the node
        
        TIME COMPLEXITY O(b^d) - assuming worst case branching factor, b, at each node as the depth, d, increases
        
        SPACE COMPLEXITY O(b^d) - O(b^(d-1)) of which are explored nodes and the remainder make up the frontier
    - - We expand the deepest unexpanded node, LIFO; The root node is expanded first before the first successor of the root and then the first successor of this node and so forth until we reach the final leaf and continue with the deepest node in the frontier - THE SAME RULE APPLIES TO NOT ADDING ALREADY VISITED CHILDREN
        
        NOT OPTIMAL - may expand an initial tree branch to get a more costly path than another would take
        
        TIME COMPLEXITY O(b^m) - where m is the maximum length of the path in the search space (generally, m is much greater than d)
        
        CAN BE COMPLETE - if there's a finite search space but isn't with infinite search space or loops
        
        SPACE COMPLEXITY - O(b^m) - as we store all the nodes from the root to the leaf
        
        IT DOESN'T SEEM IDEAL BUT WE CAN MAKE SOME ALTERATIONS
        
        DFS with less memory usage - this reduces the space complexity to O(bm) as we remove a subtree from memory once we've explored all of a subtree so only store a single path and the unexplored siblings of each node
        
        Depth Limited Search - we provide a depth limit, l, so time complexity is reduced to O(b^l). This is tricky to optimise as, if l is too small, we might not include the actual depth of the goal node, making it incomplete. If l is too large, we don't have an optimal solution and are still carrying out more steps than is necessary.