Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CS3105 AI > 1: Search > Flashcards

1: Search Flashcards

1
Q

What is a potential field?

A

A potential field is an artificially generated set of values modelling distance to the attractive goal and repulsive obstacles into scores distributed in a manner analogous to a physical field to allow for decision making on the movements of a robot AI system.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is the local minimum problem?

A

The local minimum problem is when a movement-planning AI moves into a local minimum (i..e not the true minimum, the end goal) and does not leave because the evaluation scores when moving out of the local minimum are so small for a large enough distance that it is seen as advantageous to remain in the local minimum by the system rather than seek to escape.

The problem is prevalent with local minimum movement planning systems.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is A* search?

A

A search algorithm used for pathfinding and graph traversal that has high performance and accuracy

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the BUG algorithm?

A

BUG algorithms are a set of algorithms that generally move towards the goal until the obstacle potential reaches a certain threshold, meaning they are deemed too close to an obstacle and about to collide. At this point, they “wind” by moving around the perimeter of the obstacle, along a constant obstacle potential, before unwinding on the other side of the obstacle or back at the point where the obstacle potential first passed its threshold, before winding around the obstacle.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

How does A* search surpass the local minimum problem?

A

By being able to exhaustively explore ‘good’ states on a tree that will eventually connect with the goal, where ‘good’ means minimal estimated total goal-connecting path length.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

How does BUG surpass the local minimum problem?

A

By being able to cling to obstacles and moving forwards around them like a bug crawling over a stone.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the RRT algorithm?

A

The Rapidly-exploring random tree is another algorithm for movement planning. It combines randomly chosen points with edges to form a path between a start and goal point.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How do RRTs relate to BUG and A*?

A

RRT is another motion planning algorithm that surpasses the local minimum problem common in potential fields.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the POTBUG algorithm?

A

A variant on the BUG algorithm which combines it with potential fields; it then does not return to the point at which the robot surpassed the threshold obstacle potential after moving around the obstacle, as with BUG, instead of moving towards the goal again as soon as the obstacle has been passed.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the NHBug algorithm?

A

???

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What does nonholonomic mean?

A

A nonholonomic system is one whose state depends on the path taken through past states in order to achieve the current state.

In holonomic systems, the number of controllable degrees of freedom is equal to the total degrees of freedom. The degrees of freedom of a system is the number of parameters of the system that may vary independently.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is symbolic AI?

A

Symbolic AI systems are those based on high-level human-readable (symbolic) representations of problems, logic, and searches.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What does completeness mean with respect to AI?

A

When an algorithm or system can always find a solution to a problem then it is complete.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is a heuristic?

A

A technique designed for solving a problem more quickly when classic methods are too slow, or for finding an approximate solution when classic methods fail to find an exact solution. Heuristics are not guaranteed to find a solution, i.e. complete.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is a heuristic search?

A

A search strategy that attempts to repeatedly optimise path choices using a given heuristic function and/or a cost measure.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

How can we define artificial intelligence?

A

The theory and development of computer systems able to perform tasks normally requiring human intelligence, such as visual perception, speech recognition, decision-making, and translation between languages.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is a universal search algorithm?

A

???

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is a breadth-first search?

A

Method of tree searching that involves searching each level of tree nodes in a tree one-by-one and left to right within each level.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is a depth-first search?

A

Method of tree searching that travels along each branch to its maximum depth before then backtracking and taking the next deepest branch.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is a best-first search?

A

A graph search algorithm that iteratively, at each level, examines the node with the best evaluation score first before going on to the others.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is an informed search?

A

An informed search involves using some domain-specific knowledge and an evaluation function to choose which nodes to expand and the path to examine first. You usually expand the path through the node with the best evaluation score first in a best-first search.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is an uninformed search?

A

A search which is not informed, i.e. does not use some domain-specific knowledge and an evaluation function to choose which nodes to expand and the path to examine first.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is path cost?

A

???

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is search cost?

A

???

25
Q

What is optimality?

A

The degree of quality of a solution to a problem, in respect to some predefined criteria.

26
Q

What is uniform-cost search?

A

A search algorithm that is an instance of best-first searching; the cumulative costs of moves up to and including each of the nodes being chosen from are found and the node with the smallest cumulative cost so far is then chosen to be expanded first.

27
Q

What is depth limiting?

A

When a heuristic depth bound is applied to a search algorithm, usually a depth-first search. It minimises time and space complexity, but with too shallow a depth a goal may not be reachable, so the search may not be complete.

28
Q

What is iterative deepening?

A

Using increasingly deep depth limited searches. This allows for the minimising of time and space complexity that a fixed depth search provides without risking incompleteness. Testing at each stage is relatively inexpensive. Iterative deepening is complete and optimal.

29
Q

What is bidirectional searching?

A

A search algorithm that searches in 2 directions simultaneously rather than just one. One search runs forward from the root or start node, and another runs backwards from the goal node. It can reduce time and space complexity in some cases.

30
Q

What are the space and time complexities of breadth-first searching?

A

O(b ^ d) or O(b ^ (d+1)) for both space and time complexity, where b = branching, d = depth.

31
Q

What are the space and time complexities of uniform-cost searching?

A

O(b ^ d) for both space and time complexity, where b = branching, d = depth.

32
Q

How long does it take to traverse an entire depth-first tree?

A

O(b ^ m) where b = branching degree, m = maximum depth

33
Q

How long does it take to traverse a single branch in a depth-first tree?

A

O(b * m) where b = branching degree, m = maximum depth

34
Q

When are depth-limited searches complete?

A

If a depth-unlimited search is complete and the depth bound is sufficiently large to reach the goal/solution.

35
Q

What are the time and space complexities of iterative deepening?

A

???

36
Q

What are the time and space complexities of bidirectional searching?

A

???

37
Q

What is greedy best-first searching?

A

Greedy best-first searching uses some heuristic to asses nodes being chosen between; the node with the best evaluation score from the heuristic is chosen to be expanded first.

38
Q

What is uniform cost searching?

A

A form of best-first searching. It involves expanding the node that will represent the lowest cost from the start node first.

39
Q

What are the time and space complexities of uniform cost searching?

A

???

40
Q

What are the advantages of A* searching?

A

O(b ^ (d/2)) in time

O(b ^ (d/2)) for space when an informed search

41
Q

What are the time and space complexities of A* searching?

A

???

42
Q

What is the time v memory trade-off for searching? Why is it inescapable?

A

???

43
Q

Is Uniform cost search:

a) optimal?
b) complete?
c) focused?
d) efficient?

A

Yes. Yes. No. Usually not.

44
Q

Is greedy search:

a) optimal?
b) complete?
c) focused?
d) efficient?

A

No. No. Yes. It can be efficient.

45
Q

Is A* search:

a) optimal?
b) complete?
c) focused?
d) efficient?

A

Yes. Yes. Yes. Yes, if the greedy search uses an admissible heuristic: doesn’t overestimate the cost of reaching the goal.

46
Q

If a greedy search heuristic, why then does an A* search from it never overestimate the cost from the root to the goal?

A

Because the cost from uniform cost search also forming A* is the actual cost so far and so cannot add an overestimate

47
Q

What does it mean for a function to be monotonic?

A

A function that only ever goes in 1 direction. So it can go up and be flat in inflexions but never go down, or vice versa.

48
Q

How can A* search be ensured to be optimal?

A

By ensuring it is monotonic, which in turn is ensured by making sure the greedy search it uses is monotonic.

49
Q

Why are there are single concentric contours corresponding to A* search costs?

A

A* search has no local extrema.

50
Q

What are local extrema?

A

Local maxima and minima.

51
Q

Why are the contours are focussed towards the goal by accurate greedy searches?

A

Take input as = 0 to imply non-focused circularity and add a perfect focus greedy search as a straight line metric - ovals appear.

52
Q

Why does A* search expand all nodes contour by contour?

A

Because the minimum cost node is always to be expanded next - mechanism, and the minimum cost path can always be found by expanding the nodes of the closest contour amongst the frontier nodes -desire.

53
Q

Why is it intuitively clear that A* is complete?

A

This is due to concentric contour by contour expansion not missing any states, i.e. the search is potentially exhaustive.

54
Q

Why is it intuitively clear that A* is optimal?

A

Because paths first reaching a contour where a goal state is found must contain a shortest goal-connecting path - in terms of A* cost - as contour expansion is minimal and monotonic at each stage.

55
Q

What is meant by A* being said to be optimally efficient?

A

Given the same heuristic evaluation function, no other optimal algorithm is guaranteed to expand fewer nodes than A*.

56
Q

How does A* search work?

A

Choose the next node with the minimum evaluation score, f(n), where:

f(n) = g(n) + h(n)
g(n) = cost from start point to the next node
h(n) = heuristic estimate of cost from next node to end goal
57
Q

How does RRT search work?

A

Given a start and end goal point or region. While within the limit of the max number of iterations, generate a new random position within max linking distance from existing nodes; not the method of finding random new positions is a design choice that affects the algorithm. If it’s within an obstacle, continue. Otherwise, link the new point to the nearest existing node with a new edge (or multiple). Stop when a new linked node reaches the goal and return the path to that node from the initial one.

58
Q

What is an 8-puzzle?

A

Given a 3x3 grid of numbers 1-8 and an empty cell, how do you move the cells to be 1-8 left to right, top to bottom, in as few moves as possible.

CS3105 AI (8 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions