CS255 - Artificial Intelligence

What are some inputs to an agent?

• Abilities (set of actions it can perform)

• Goals/preferences (wants, desires, values)

• Prior knowledge (what it comes knowing, what it doesn’t get from experience)

• Stimuli

  • Current (information from current environment)

  • Past experiences (information from past)

How is rational action defined for agents?

• It is is whichever action maximises the expected value of the performance measure given the percept sequence to date

  • (i.e., doing the right thing)

  • Can heavily rely on previous perceptions

Why are rational agents not expected to be omniscient?

• Because unexpected situations occur in dynamic environments

• A rational agent needs only to do its best given the current percepts

Why are rational agents not expected to be clairvoyant?

• An agent is not expected to foresee future changes in its environment

Why are rational agents not expected to be successful?

• Rational action is defined in terms of expected value, rather than actual value

• A failed action can still be rational.

What is modularity as a dimension of complexity and what are its values?

• It is the level of how specialised/independent the internal structure of the rational agent is (into different units)

• Flat - only one level of abstraction

• Modular - interacting modules that can be understood separately

• Hierarchical - modules are recursively decomposed into other modules

  • One module relies on other modules, and is relied upon by different other ones

What is planning horizon as a dimension of complexity and what are its values?

• It is a measure of how far into the future the agent looks before deciding what to do

• Static - world does not change

• Finite stage - fixed number of time steps

• Indefinite stage - finite (but not predetermined) number of time steps

• Infinite - expected to go on forever

What is representation as a dimension of complexity and what are its values?

• The internal encoding of knowledge or states of the world that allows the agent to reason

• Explicit states - one way the world could be

• States through interpreting features

  • Such as ML feature vectors based on environment

• States through defining relations between agents or individuals

What are computational limits as a dimension of complexity and what are its values?

• The bounds on computation that agents must consider before reasoning or making a decision

• Perfect rationality - agent can determine best course of action without exhausting computational resources

• Bounded rationality - agent needs to consider computational and memory limitations to make decisions

What is experience as a dimension of complexity and what are its values?

• Defines whether or not the model is specified knowledge or if they need to develop it before decisions

• Knowledge is given - priori is fully specified

• Knowledge is learned - requires some sort of learning technique

What are the 2 dimensions for uncertainty and what levels of uncertainty can an agent have?

• Two dimensions - sensing and effect

• No uncertainty - agent knows what is true

• Disjunctive uncertainty - set of possible states

• Probabilistic uncertainty - probability distribution over the worlds

Why is probability significant for an agent?

• Agents must act even if they are uncertain

• It allows for the best judgement in uncertain situations

• Probabilities can be learned from data and prior knowledge

What is sensing uncertainty as a dimension of complexity and what are its values?

• It describes how well an agent can gain information from observing stimuli 

• Fully observable - the agent can observe the state of the world

• Partially observable - various states are possible given the agent’s stimuli

What is event uncertainty as a dimension of complexity and what are its values?

• It is how effective an agent is at predicting the resulting state given its initial state and the actions it takes

• Deterministic - resulting state is determined from the action & state

• Stochastic - uncertainty about the resulting state

What are preferences as a dimension of complexity and what are its values?

• It describes what the agent’s goals are and what it wants to achieve

• Achievement goal = goal the agent wants to meet

  • Can be a complex formula

• Complex preferences may involve tradeoffs between desired things (at different times)

  • Ordinal = only order matters

  • Cardinal = absolute values matter too

What is number of agents as a dimension of complexity and what are its values?

• Whether or not multiple agents need to be taken into account

• Single agent reasoning means we abstract other agents as part of the environment

• Multiple agent reasonings means we need to strategically reason about other agents’ motives and actions

What is interaction as a dimension of complexity and what are its values?

• It is a measure of when the agent reasons to decide what to do

• Offline = not while it is acting

• Online = while it interacts with the environment

How does modularity interact with uncertainty and succinctness?

• Some levels may be fully observable whilst some may only be partially observable

• This means that a full understanding of the model won’t always be possible

What values of dimensions make the reasoning simpler for the agent?

• Hierarchical reasoning

• Individuals and relations

• Bounded rationality

What should a representation be?

• It should have an accurate representation of the world

• Deep enough to have the knowledge to solve the problem

• As close to the problem as possible:

  • Compact, natural, maintainable

• Amenable to efficient computation

  • Able to express features of the problem that can be exploited for computational gain

  • Able to trade-off accuracy/computation time/space

• Able to be acquired from people, data and past experiences

For a given problem description, what are the potential classes that each solution can be placed in?

• Optimal → best solution (according to some measure of quality)

• Satisficing → good enough to be considered (based on some measure of what is adequate)

• Approximately optimal → quality is close to the best that is theoretically possible

• Probable → likely to be a solution

What is an anytime algorithm?

• An algorithm that can provide a solution at any time

  • Given more time, it can provide a better solution

What needs to be considered when mapping from problem → representation?

• Level of abstraction that the problem needs to represent

• Individuals and relations that need to be represented

• Representation of knowledge

  • How can it be natural, modular & maintainable?

• Methods of acquiring the required information

  • Data, sensing, experience etc.

What needs to be considered when choosing the level of abstraction?

• Does it need to be specified and understood by people?

  • Higher level is better (but it is less descriptive)

• Do we need a more accurate/predictive description?

  • Lower level is better (but harder to reason with)

  • We may not know all the information needed

What do we mean by reasoning?

• It is the computation required to determine what an agent should do

What are the different types of computation?

• Offline computation = computation done by the agent before it has to act

  • Likely needs to make use of background knowledge and data stored in some knowledge base

• Online computation is the computation done by an agent between receiving information and acting

How does an agent system work and interact?

• Agent system is made up of the agent and its environment

  • Agent receives stimuli from the environment

  • Agent performs actions in the environment

How can an agent be simplified into a model comprising of a body and controller?

• Body is what interacts with the environment 

  • Sensors interpret stimuli

  • Actuators carry out the actions

• Controller receives percepts from the body, and sends commands to the body

  • Body can have reactions that aren’t directly controlled

What is the significance of a controller for an agent and what limitations do they have?

• Acts as the brains of the agent 

• Controller specifies the command at every time

  • Commands depend on current/previous percepts

• They are limited by memory & computational capabilities

What are the different agent function (w.r.t. to some time point T)?

• Percept trace = sequence of all past, present and future percepts received by controller

• Command trace = sequence of all past, present and future commands outputted by controller

• Transduction = function that maps percept traces → command traces

  • It is causal if the command trace up to T is based on percepts up to T

  • Controller is an implementation of a causal transduction

• Agent history at T is a sequence of past and present percepts/commands

What is a belief state in reference to an agent?

• It is an encoding of all the agent’s history that it has access to

• It encapsulates information about the past to use for current and future actions

  • Current information can be used to update its memory and therefore belief state

What is a belief state function?

• Function that uses the existing belief state and current percepts to return the next (updated) belief state

What is a command function?

• Function that uses the existing memory and current percepts to decide on the action that the agent needs to take 

How does a hierarchical structure of controllers work (as opposed to just one controller)?

• Each controller sees the controllers below it as a “virtual body” from which it gets percepts and sends commands

• Each controller delivers high-level precepts to the controllers above it, and low-level commands to the controllers below it

  • Lower level controllers run faster and react to the world more quickly

  • They also a deliver a simpler, abstracted view to the higher-level controllers

What are the 3 functions implemented in each layer of a controller?

• All rely on 3 parameters: existing memory, current percept & current command

• Memory function

  • Decides what to remember

  • Takes in new information and/or discards old information

• Command function

  • Decides what commands to deliver to the lower-level layers

• Percept function

  • Decides what percepts to deliver to the higher-level layers

What is meant by a problem-solving agent?

• A goal-based agent that will determine sequences of actions that lead to desirable states

What are the 4 steps that a problem-solving agent must take?

• Goal formulation

  • Identifying the goal given the current situation

• Problem formulation

  • Identifying permissible actions/operations, as well as the states to consider

• Search

  • Finding the sequence of actions to achieve the goal

• Execution

  • Performing the actions in the solution

What are the 2 types of problem solving?

• Offline → complete knowledge of problem & solution

• Online → acts without complete knowledge of problem & solution

What is a single-state problem?

• Deterministic and fully observable

  • Sensors tell agent the current state and it knows exactly what its actions do 

  • So it knows exactly what the state will be in after any action

What is a multi-state problem?

• Deterministic but partially observable

  • Limited access to state but it knows what its actions do

  • The set of states resulting from an action can be determined

  • Sets of states are manipulated as opposed to a single state (since we don’t know what the exact resulting state will be)

What is a contingency problem?

• Stochastic and partially observable 

  • Current state is not known and neither is the resulting state from the action

  • Execution will require sensors

  • The solution will be a tree with branches for contingencies

  • Search & execution will typically be interleaved

What is an exploration problem?

• Unknown state space and knowledge must be learned

  • Agent won’t know what its actions will do

What is defined inside of a state-space problem?

• Set of states

  • Includes a subset of states known as the start states

• Set of actions

• Action function

  • Given a state and an action, it will return a new state

• Set of goal states

  • Specified as per the goal test function

• Criterion to specify the quality of an acceptable solution

What abstract fields can be used to select a state space?

• Fields of the state space that are abstracted from the real world for problem solving

• Abstract state should be similar to the set of real states

• Abstract operators should be similar to the combination of real actions (including all possible actions that need to be taken)

• Abstract solution should be similar to the set of paths that are solutions in the real world

What is meant by uninformed search?

• The most basic approach to problem solving

• Is an offline, simulated exploration of the search space

• Starts from a start state and then expands one of the explored states by generating its successors

  • Goal is to form a search tree, with goal state being one of the nodes

How does breadth-first tree search work?

• We expand the shallowest unexpanded node

• We place the successors at the end of the queue 

  • Essentially a level-order traversal of the state space

What is the completeness, complexities and optimality of the BFS tree search?

• The tree search is complete — it will find the solution if the branching factor is finite

• Time complexity is O(b^d) where b = branching factor and d = depth

• Space complexity is O(b^d) since we need to store all possible generated nodes

  • This is the main problem here

• Generally not optimal — only optimal if cost is a non-decreasing function of depth

How does depth-first tree search work?

• We expand the deepest unexplored node

• Successors are inserted at the front of the queue 

What is the completeness, complexities and optimality of the DFS tree search?

• Not complete as it fails in infinite-depth spaces and spaces with loops

  • Needs to be modified to avoid repeated states on a path

• Time complexity is O(b^m) which is much worse when m > d

• Space complexity is O(bm) which is much better than BFS

• Not optimal

How does DFS differ from BFS in how they treat the frontier of nodes?

• DFS treats the frontier like a stack — it selects one of the last elements added to the frontier

  • We only select subsequent paths if the path at the top of the stack is fully explored

• BFS treats the frontier like a queue

  • We select the earliest path and add its neighbours to the end of the queue

How does a lowest-cost graph search work?

• Algorithm selects a path on the frontier with the lowest-cost

• Frontier is a priority queue that is ordered by cost

• First path to a goal will be the path that has the lowest total cost across its arcs

  • We do BFS if the arc costs are equal

How does a heuristic search work?

• Includes distances from each node to the goal and then determines priority based on that

How does the best-search function implement heuristics logic?

• It determines best path based on solely the heuristic function

• Time complexity is O(b^n)

How does A* search combine heuristics with path cost?

• Combines the cost of each path with the heuristic value of that node from the goal state

  • Both are summed into f(p) for each path

• Priority queue ordering is based on f(p) values

What is an admissible algorithm?

• A search algorithm is admissible if, whenever a solution exists, it returns an optimal solution.

What conditions must A* meet to be admissible?

• Branching factor is finite

• Arc costs are bounded above zero (there is some ϵ > 0 such that all of the arc costs are greater than ϵ)

• h(n) is admissible, i.e., it is nonnegative and an underestimate of the cost of the shortest path from n to a goal node.

How is A* algorithm always able to find a solution if it exists?

• Frontier always contains initial part of a path to a goal before that goal is selected

• A* halts since the cost of the paths on the frontier keep increasing and will exceed any finite number 

• Admissibility ensures that the first solution found will be optimal, even in graphs with cycles.

What are the complexities of A* search?

• Time: O(h*n)

• Space? O(k^n)

  • All nodes are kept in memory

How does cycle pruning work?

• Involves revisiting a node already on the current path without losing optimality

• We don’t add cyclic paths to the frontier

• Cycle checking done in constant-time via DFS

How does multiple path pruning work?

• We prune a path to node n if the path to it was already found

• Algorithm keeps an explored (closed) list of nodes from expanded paths

  • Initially empty 

  • When expanding a path from n0 → nk, we discard the path if it is in the closed list, or we add it to the closed list and continue normally

What do we mean by a consistent heuristic?

• Any that satisfies the monotone restriction:

  • h(n) ≤ cost(n, n ′ ) + h(n ′ ) for any arc ⟨n, n ′ ⟩

• When A* follows this, it means that the first path found to a node is the lowest-cost path to that node

What is meant by the forward and backward branching factor?

• Forward branching factor: number of arcs out of a node

• Backward branching factor: number of arcs into a node

How can DP be used for graphs?

• For static graphs build a table of dist(n), the actual distance of the shortest path from node n to a goal

What are the issues of using DP here?

• Dynamic programming requires enough space to store the whole graph

• The dist() function needs to be recomputed for each goal.

What is bounded DFS?

• A DFS that takes a bound (cost or depth) and does not expand paths that exceed the bound

  • Explores part of the search graph

  • Uses space linear in the depth of the search

What is iterative-deepening search?

• Algorithm that uses bounded DFS but with a bound increasing by 1 every time the solution cannot be found

• Uses linear space with an asymptotic overhead of (b/b-1) times the cost of expanding the nodes at depth k using breadth-first search

How does depth-first branch and bound work?

• Combines depth-first search with heuristic information

• Finds an optimal solution

• Most useful when there are multiple solutions, and we want an optimal one

• Uses the space of depth-first search.

How is the bound initialised with depth-first branch and bound?

• Initialise it to infinity

• The bound can be set to an estimate of the optimal path cost

• Either finds a solution or doesn’t and can either prune a path or not

What do we mean by an effective branching factor?

• It is the branching factor a uniform tree of depth d would have to contain N nodes.

What does it mean when one heuristic hx dominates another one hy?

• When all hx(n) >= hy(n)

In the context of heuristics, what is the cost of some subproblem in terms of the cost of some other problem?

• It will be a lower bound on the cost of a complete problem

What do we mean by a CSP (constraint satisfaction problem)?

• It is a problem that involves a set of variables

  • The variables all have a domain of possible values and some hard constraints

• Involves finding a single solution where assigning this value onto all the variables will satisfy the constraints

• The constraints specify legal combinations of the values of variables

How does a CSP work as an optimisation problem?

• There is a function that gives a cost for each assignment of a value to each variable

• The solution assigns the value to all variables where the value minimises the cost function

How are discrete variables work as a type of CSP?

• They have finite domains

  • n variables of size d → O(d^n) complete assignments 

• They have infinite domains (integers, strings etc)

  • Not all possible assignments can be enumerated, needs linear constraints 

How are continuous variables work as a type of CSP?

• The domain is continuous (so it is uncountable)

• Linear constraints are solvable in polynomial time through linear programming methods

What are the different types of constraints in relation to CSPs?

• Unary constraints

  • These involve a single variable

• Binary constraints

  • These involve a pair of variables

• Higher-order constraints

  • Involves 3 or more variables

• Preferences/soft constraints

  • Comparing one value as opposed to another

What are some real-word examples of CSPs?

• Assignment problems

• Timetabling/scheduling

• Configuration problems

• Spreadsheets

What is backtracking and how can it be used to solve a CSP?

• It is the basic uninformed algorithm for CSPs

• Explore the assignment space by instantiating the variables one at a time

• Evaluate each constraint predicate as soon as all the variables are bound

• Prune the partial assignments — they are not included in the solution

  • We recur backwards and try other potential assignments

How can DFS be used to apply backtracking for a CSP?

• Complete state formulation is used to track the whole state and keep manipulating that state

• Since variable assignments are commutative, we only need to consider assignments to a single variable at each node

What is minimum remaining values (MRV) as a CSP backtracking heuristic?

• Aim is to choose the variable with fewest legal values

• It will pick the variable most likely to fail first — if there is a variable with 0 possible assignments it will pick that and fail immediately

What is the degree heuristic as a CSP backtracking heuristic?

• It acts as a tiebreaker amongst the MRV variables

• We choose the variable with the most constraints on remaining variables

• This is then used to try and reduce the branching factor of future choices

What is least constraining value (LCV) as a CSP backtracking heuristic?

• Given a variable, we choose the least constraining value

• This is the one that rules out the fewest values in the remaining variables

How can CSPs be solved via a graph search?

• We model nodes as an assignment of values — they correspond to the state of the world

  • This can be the assignment of certain values

• We then select a variable (y) that is not assigned in the node

• Search beings with start node (whichis the empty assignment)

• Goal node is a total assignment that satisfies all the constraints

How does the constraint network function?

• There is a node for each variable (circular) and constraint (rectangular)

• Domain of values is associated with each variable node

• The arcs go from a variable to a constraint that involves that variable

How do consistency algorithms work in CSPs?

• Goal is to prune the domains as much as possible before selecting values from them

• They rely on the idea of arc consistency

• This is when we have 2 variables X, Y and every value in the domain of X has at least one matching value in Y that meets the needed constraints

How do we make a network arc consistent?

• Go through the potential pairings 

• If there are values that don’t work as solutions to a problem we can remove them 

  • When we remove, the domain will be reduced so we need to go back and check again

How would solutions need to be found when arc-consistency finishes?

• If domains have more than one element, we will need to search

• The domain can also be split in half and recursively solved, one by one

What is the difference between hard and soft constraints?

• Hard constraints are designed to be met by some variables

• Soft constraints involve costs of arcs/nodes that need to be minimised

How can problems be made more feasible by splitting them into subproblems?

• For a subproblem involving c out of n total variables, we have n/c lots of them

• Each take at most d^c to solve so worst-case solution is n.c * d^c

• This is much smaller than d^n making it more feasible

How can CSPs be solved by structuring them as trees?

• Same logic of breaking them down into subproblems 

• Time complexity goes from O(d^n) to O(n * d^2)

What would the algorithm for tree-structured CSPs look like?

• Start with a root variable

• Order the variables from root to leaves

• This means every node’s parent precedes it in the ordering

How does cutset conditioning work on graphs that are not quite trees?

• A set of variables is instantiated in all possible ways such that the remaining constraint graph is a tree

• Its neighbours’ domains are then pruned so that the remainder is a tree

• A cutset of size c will run in O(d^c (n-c)d²)

  • This makes it extremely fast for small c

How does the variable elimination algorithm work?

• The idea is that we need to eliminate the variables one-by-one and pass constraints to their neighbours

• Case 1 — one variable only

  • Return the intersection of the unary constraints that contain it

• Case 2 — more than one variable

  • Select it, call it X

  • Combine all constraints that involve X into one single joint constraint.

  • Eliminate X by only keeping combinations of the remaining value that satisfy constraints

  • Add the resulting reduced constraint back into the CSP

  • Recursively repeat until variable is deleted — all values are gone

How does local search work?

• Only focuses on goal state

• Uses a single current state and moves to neighbours of that state

• Useful for optimisation problems (finding the best state according to some objective function)

What is an iterative improvement algorithm?

• An algorithm that seeks to find a particular configuration or a subset of configuration

  • We are only focused on the configuration that meets the standard

  • Each step of the way, we consider the current configuration and try to improve it

• The state space is the set of complete configurations

• Works both online and offline

How does a hill-climbing algorithm work?

• Similar to a iterative improvement algorithm — the aim is to improve the state or reduce the cost in the next state

• Move in the direction of whatever brings the value closer to the goal 

• No search tree — only uses the current state and its cost 

  • Tie-breaker is to just choose at random

What are som issues of a hill-climbing algorithm?

• At local maxima, the algorithm will halt with a suboptimal solution

  • This occurs especially once we begin AFTER the global maximum

• When ridges are involved, the search might oscillate from side-to-side as opposed to straight up

  • We end up never reaching the true altitude

• It will follow a random walk on plateaus

  • If progression is possible, we use sideways moves to get off the plateau (shoulder)

How can local search be done using a Greedy descent?

• Goal — find an assignment with 0 conflicts (conflict = violated constraint)

• Heuristic function = # of conflicts; we need to minimise this

• We assign a value to each variable, then select a variable to change and select a new value for that variable

• Terminates when a satisfying assignment is found

What happens when the domains are continuous for greedy descent?

• Gradient descent will change each variable proportionally to the gradient of the HEURISTIC function in that direction

• This is done by taking the partial derivative of the heuristic function, to then move a number of steps in that direction

How does randomised greedy descent work (in relation to greedy descent?

• Works as a form of greedy descent with extra allocations

• We can have random walk in which we move to a random neighbour with a random # of steps

  • Performs poorly at escaping local minima when they’re far apart, but better when many are close together.

• Random restart also allowed — reassigns random values to all variables

  • Finds the optimal value quickly when minima are far apart but can get stuck on peaks otherwise