CS3033 - Artificial Intelligence

Question 1

What is Moravec’s Paradox?

Answer 1

High-level (“human”) reasoning requires little computation while sensor motor reasoning is comparatively much harder. AKA Things humans find easy machines find hard and vice versa`

Question 2

What is rational behavior?

Answer 2

Doing the “right thing”. The right thing: that which is expected to maximise goal achievement, given the available information

Question 3

What is an agent?

Answer 3

An entity that perceives and acts independently. AKA takes input and performs actions based on it. A rational Agent will attempt to perform the action that maximises goal achievement.

Question 4

What is a Multiagent system

Answer 4

A multiagent system is one that consists of a number of agents, which interact with one-another. In the most general case, agents will be acting on behalf of users with different goals and motivations. To successfully interact, they will require the ability to cooperate, coordinate and negotiate with each other

Question 5

What is a reactive system

Answer 5

A reactive system is one that maintains an ongoing interaction with its environment, and responds to changes that occur in it (in time for the response to be useful); i.e. in real time

Question 6

Define Accessability/Observability

Answer 6

An accessible or fully observable environment is one where an agent can obtain complete, accurate, up-to-date information about the environment’s state.

Question 7

Define a Deterministic environment

Answer 7

A deterministic environment is one where each action has a single guaranteed effect. There is no uncertainty about the state that will result from performing an action

Question 8

Define Episodic enviroment

Answer 8

An episodic environment in one in which the next action taken by the agent does not depend on the previous action. E.g. detecting defects on an assembly line

Question 9

Define Sequential enviroment

Answer 9

An agents decision could affect all future decisions made by the agent.

Question 10

Define static vs dynamic

Answer 10

A static environment is one where the time where an agent decides what action to take, the environment does not change. Semi-dynamic environments are when the environment does not change by the agent’s performance score does. Ex: chess clock

Question 11

Discrete vs Continuous

Answer 11

A discrete environment can can be abstracted into countable variables measuring the qualities of the environment.

Question 12

Known vs Unknown

Answer 12

A known environment: all outcomes from all actions are given. Unknown: the agent will have to learn as it goes

Question 13

Define a simple reflex agent

Answer 13

Selects an action based on the current precept. History is not considered. Only works in a fully observable enviroment

Question 14

Define model-based reflex agents

Answer 14

Maintains an internal state using a transition and sensor module.

Question 15

Goal-based agent

Answer 15

Extends model-based reflex agent. Stores the goal state and uses it to inform it’s next action.

Question 16

Utility-based agent

Answer 16

Will choose the action that maximises the expected utility of the action outcomes.

Question 17

What is an uninformed search algorithm?

Answer 17

An algorithm that does not rely on a heuristic function, so it exhausts the state space finding for the goal state. BFS being an example.

Question 18

How is a search problem formulated. (Four steps)

Answer 18

Goal formulation, problem formulation, search, execution. Think back to programming assessment

Question 19

How do we measure how good a search algorithm is? (four points)

Answer 19

Completness, Optimality, time complexity, space complexity.

Question 20

Explain Breadth First Search

Answer 20

Start from root node, explore all neighbouring nodes and expand them. BFS is complete in graph search if state space is finite but can get stuck on infinite loop in tree search

Question 21

Explain Uniform Cost Search

Answer 21

It acts same as BFS but expands the node with the lowest path cost (cost to get from start node to node), this is done using a priority queue.

Question 22

Explain Depth First Search

Answer 22

Explore the deepest node, backtrack when a dead end is reached. Variations include include Depth Limited Search and Iterative Deepening Depth-first Search.

Question 23

Explain Iterative Deepening Depth First search

Answer 23

Combines benefits of BFS and DFS, by acting as a DFS with a gradually increasing limit until goal is found. It’s optimal and complete.

Question 24

What is an informed search algorithm?

Answer 24

An algorithm that uses a heuristic function to make informed decisions when selecting a state to move to. It aims to move in the direction of the goal state and get closer to it at each move.

Question 25

Explain the difference between Greedy-Best and A* search

Answer 25

Greedy best makes use of the heuristic function only so the estimated cost is the heuristic cost f(n) = h(n), while A* uses the sum of the cost to reach the current state from the initial state plus the estimated cost to reach the goal state from the current state, namely f(n) = g(n) + h(n)

Question 26

Explain heuristic admissibility?

Answer 26

Never overestimates the cost

Question 27

Explain heuristic dominance?

Answer 27

A measure of which heuristic is more efficient

Question 28

Define local search and its advantages

Answer 28

Does not keep track of paths. Only cares about the final state, not the path to get there. Does not search the entire space

Advantages:
Low memory cost
Good for infinite or very large state spaces

Disadvantages:
Not optimal

Question 29

Explain Hill Climbing algorithm?

Answer 29

It aims to move in the direction with the steepest ascent on the state space graph. Issues arise when the state space graph contains plateaus, ridges, and local maxima since the algorithm may terminate prematurely. Solutions are to allow sideways moves, stochastic hill climbing and random restart hill climbing.

Question 30

Explain Simulated Annealing?

Answer 30

Apply a random walk to hill climbing. Have a tolerance to move to a less than optimal state but decrease this tolerance at each iteration in hope of finding a global maxima. It is both efficient and complete.

Question 31

Explain Local Beam Search?

Answer 31

The algorithm works the same as a BFS, except that it will select the best k states from the states generated for each node. Since each node expanded is based on the previous k expanded nodes, there’s a risk that the search is clustered in a specific state space region. Stochastic LBS is a solution.

Question 32

What are the 4 types of crossovers in genetic algorithms? Briefly explain.

Answer 32

1-point crossover : choose a random point on parents and swap their tails around
n-point crossover : choose n random crossover points and swaps along those points and attaches alternating pairs
uniform crossover: assign heads to one parent and tail to other, then do a coin flip to assign each gene and assign its inverse to the parent
mutations : pick the best portions from two genes and hope to get a better gene out.

Question 33

Explain the difference between crossover and mutation?

Answer 33

Crossover is exploratory and combines information from two parents, mutation is exploitative and introduces new information in the genes.

Question 34

Why do Local Search algorithms fail in continuous state spaces?

Answer 34

Because there’s an infinite branching factor for each node expansion. To fix: use a discretization method to abstract a continuous space into a discrete one.

Question 35

Explain the two variations of multi-agent environments?

Answer 35

Agents can be cooperative or competitive

Question 36

What are the key ingredients in Game Theory (Three factors)

Question 37

What are the two standard representations

Question 38

What is a dominant strategy in game theory. (Prisoners dilemma)

Question 39

What is the Nash Equilibrium in Game Theory

Question 40

How can transitions be modelled in a non-deterministic search (Sucky suck)

Question 41

Describe adversarial search and MINMAX strategy

Question 42

What are two strategies reduce complexity in adversarial search

Question 43

What are the 5 components of a constraint satisfaction problem

Question 44

What are the three types of solutions to a CSP

Question 45

Name an example of Incremental standard search formulation in CSPs and explain it

Question 46

What are three improvements to the performance of backtracking search

Question 47

Explain local search for CSPs. Explain Min-conflict heuristic, plateau search and constraint weighing,

Question 48

What are the five requirements of a knowledge based agent

Question 49

Explain inference via enumeration

Question 50

Explain forwards and backwards chaining

Question 51

What are the three failure causes due to large domains. (Probabilities over time)

Question 52

What is decision theory