Robotics Flashcards by Thomas Collins

What is the definition of a robot?

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

How well did you know this?

Not at all

Perfectly

What are some problems in robotics?

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

How well did you know this?

Not at all

Perfectly

What is a state called in robotics?

A pose (position plus orientation)

How well did you know this?

Not at all

Perfectly

What does path planning do?

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

How well did you know this?

Not at all

Perfectly

What does motion planning do?

Path planning plus time (speed & acceleration)

How well did you know this?

Not at all

Perfectly

What do more complex robots require?

More complex planning

How well did you know this?

Not at all

Perfectly

What is the piano mover’s problem?

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?

Not at all

Perfectly

What are some applications that might want to cover space?

Vacuum cleaners
Lawn mowers
Harvesting
etc

How well did you know this?

Not at all

Perfectly

How do space covering applications work?

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?

Not at all

Perfectly

What is a PSPACE problem?

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

How well did you know this?

Not at all

Perfectly

What is a PSPACE hard problem?

At least as difficult as the hardest problems in PSPACE

How well did you know this?

Not at all

Perfectly

What is a PSPACE-complete algorithm?

The hardest problems in PSPACE

How well did you know this?

Not at all

Perfectly

What is a complete algorithm?

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

How well did you know this?

Not at all

Perfectly

What is a resolution complete algorithm?

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?

Not at all

Perfectly

What is a probabilistically complete algorithm?

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?

Not at all

Perfectly

What are bug algorithms roughly inspired by?

Insect capabilities

How well did you know this?

Not at all

Perfectly

What are all the things that a robot can do?

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)

What is the bug 0 (common sense) algorithm?

Head towards goal
Turn when encountering an obstacle
follow obstacle until able to head to goal
Repeat until goal reached

What are some characteristics of the common sense algorithm?

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

What is the bug 1 (complete) algorithm?

Head towards goal
Turn when encountering an obstacle
Follow obstacle until coming back to first contact, while remembering point closest to goal (leave point)
Go to leave point
Repeat until goal reached or cannot go to goal from leave point

What are some requirements of the bug 1 algorithm?

Memory of locations
Distance to goal

What is the cost of the bug 1 algorithm?

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

What is the bug 2 algorithm?

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

What is the bug 2 cost?

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

What are some differences between bug 1 and 2?

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

What does configuration space try to do?

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

What is configuration q of a robot?

A vector of parameters that specify the configuration

What does configuration allow for?

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

What is configuration space?

The space of all possible configs of the robot

What do potential field planners do?

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

What are some advantages of the gradient descent algorithm?

Computationally fast Smooth paths (when it works)

What are some disadvantages of the gradient descent algorithm?

- Solution not guaranteed - Manual tuning sometimes required - Not complete

What is a cost map in 3D mapping?

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

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

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

What does global planning do?

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

How does local trajectory work?

- 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

What was the dynamic window approach?

- 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

What is the LAGR approach?

- 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

How does the ExoMars path planning work?

- 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

Is the bug 1 algorithm complete?

Yes