Brainscape's Knowledge GenomeTM

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


See full index

CS319 Advanced Algorithms > Robotics > Flashcards

Robotics Flashcards

1
Q

What is the definition of a robot?

A

A physical agent that:
- Can sense
- Can act in an intelligent manner in its environment
- Is programmable

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

What are some problems in robotics?

A

Sensing
Mapping and localisation
Navigation (PLANNING and control)
Safety
Reliability

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

What is a state called in robotics?

A

A pose (position plus orientation)

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

What does path planning do?

A

Plans a sequence of movements from a starting pose to a goal pose

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

What does motion planning do?

A

Path planning plus time (speed & acceleration)

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

What do more complex robots require?

A

More complex planning

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

What is the piano mover’s problem?

A
  • The classical path planning problem
  • It has a rigid body
  • A complex shape in complex environments
  • Only geometric considerations
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What are some applications that might want to cover space?

A

Vacuum cleaners
Lawn mowers
Harvesting
etc

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

How do space covering applications work?

A

The path must go through all points in the space (and avoid obstacles)
These points may be big
There can be specific constraints such as uniform coverage, regular or random etc

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

What is a PSPACE problem?

A

A class of problems that can be solved in poly space
(same as P problems but for space)

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

What is a PSPACE hard problem?

A

At least as difficult as the hardest problems in PSPACE

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

What is a PSPACE-complete algorithm?

A

The hardest problems in PSPACE

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

What is a complete algorithm?

A

An algorithm that always finds a solution in finite time if it exists, or returns no solution

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

What is a resolution complete algorithm?

A

An algorithm that always finds a solution in finite time for some (fine) resolution discrete version of the problem if a solution exists, or says there is no solution

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

What is a probabilistically complete algorithm?

A

An algorithm where the probability of finding a solution converges to 1 as running time approaches infinity, if a solution exists

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

What are bug algorithms roughly inspired by?

A

Insect capabilities

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

What are all the things that a robot can do?

A

Know its current position in global map
Know its goal position in global map
Can compute the direction to its goal
Can sense obstacles
Drives using a small set of behaviours (follow wall, drive to point etc)

18
Q

What is the bug 0 (common sense) algorithm?

A
  1. Head towards goal
  2. Turn when encountering an obstacle
  3. follow obstacle until able to head to goal
  4. Repeat until goal reached
19
Q

What are some characteristics of the common sense algorithm?

A

Touch sensing only
Knows direction to goal
Fully reactive
No memory
Not complete

20
Q

What is the bug 1 (complete) algorithm?

A
  1. Head towards goal
  2. Turn when encountering an obstacle
  3. Follow obstacle until coming back to first contact, while remembering point closest to goal (leave point)
  4. Go to leave point
  5. Repeat until goal reached or cannot go to goal from leave point
21
Q

What are some requirements of the bug 1 algorithm?

A
  • Memory of locations
  • Distance to goal
22
Q

What is the cost of the bug 1 algorithm?

A

D + 1.5(sum (Pi))
Where D is distance, start to goal
Pi is perimeter length of obstacle i

23
Q

What is the bug 2 algorithm?

A

Find the line connecting start and goal (m-line)
1. Head towards goal on m-line
2. Turn left/right when encountering an obstacle (hit point)
3. Follow the obstacle until finding the m-line again, closer to goal
4. Repeat until reaching goal or re-encountering previous hit point

24
Q

What is the bug 2 cost?

A

D + 0.5(sum(ni * Pi)
Where D is distance, start to goal
Pi is perimeter of obstacle i
ni is number of m-line intersections with obstacle i

25
Q

What are some differences between bug 1 and 2?

A

1 does exhaustive search while 2 is greedy

2 is in many cases better, especially simple cases

1 is more predictable and performs better in more complex cases

26
Q

What does configuration space try to do?

A

Specifies a robot in its environment such that a collision free plan can be created

27
Q

What is configuration q of a robot?

A

A vector of parameters that specify the configuration

28
Q

What does configuration allow for?

A

The complete specification of the position of every point of the robot

29
Q

What is configuration space?

A

The space of all possible configs of the robot

30
Q

What do potential field planners do?

A

Build some surface in C-Space where the lowest point is the goal
Obstacles create high points
Robot is modelled as a ball that rolls down

31
Q

What are some advantages of the gradient descent algorithm?

A

Computationally fast
Smooth paths (when it works)

32
Q

What are some disadvantages of the gradient descent algorithm?

A
  • Solution not guaranteed
  • Manual tuning sometimes required
  • Not complete
33
Q

What is a cost map in 3D mapping?

A

Grid with cells containing a number which represents the cost of traversing the cell
Cost could be due to factors such as obstacles, known/unknown area, nature of ground, hills etc

34
Q

What is the algorithm for the wave front algorithm with cost?

A
  1. Initialise goal with 0 and all other cells with infinity
  2. Push goal on ‘open’ list
  3. Pop cell from ‘open’ list and calculate the values of its neighbours
  4. If value of neighbour lower than previously stored, update to new value and push neighbour on the list
  5. Repeat from 3 while list is not empty
35
Q

What does global planning do?

A

Uses gradient descent in the wave-front grid to produce path
Ignores dynamics of the robot

36
Q

How does local trajectory work?

A
  • Turns global path into a series of local trajectories
  • Based on testing what can be done from in current configuration
  • Optimisation based on things like cost
37
Q

What was the dynamic window approach?

A
  • Searches all possible paths, with constant velocities for some time
  • Evaluate each retained path based on heading to goal, distance to obstacles and velocity
  • Keep best
  • Transform this best velocity into robot control
  • Repeat
38
Q

What is the LAGR approach?

A
  • Simulate the motion of the robot performing all possible actions for a short period of time
  • Eliminate actions that result in hitting an obstacle
  • Choose best action based on cost, dist to goal, dist to path and velocity
39
Q

How does the ExoMars path planning work?

A
  • Produce a sequence of simple possible paths
  • First, one of a possible 8 point turns (on the spot) every 45 deg
  • Then, 3 smooth curves each one of a possible 9 curvatures (4 either side of straight)
  • Finally, straight line towards goal
  • Only initial point turn and 2 first smooth curves sent to controller
  • A* used to find best based on cost and dist to goal
40
Q

Is the bug 1 algorithm complete?

A

Yes

CS319 Advanced Algorithms (8 decks)

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