Robotics Flashcards
What is the definition of a robot?
A physical agent that:
- Can sense
- Can act in an intelligent manner in its environment
- Is programmable
What are some problems in robotics?
Sensing
Mapping and localisation
Navigation (PLANNING and control)
Safety
Reliability
What is a state called in robotics?
A pose (position plus orientation)
What does path planning do?
Plans a sequence of movements from a starting pose to a goal pose
What does motion planning do?
Path planning plus time (speed & acceleration)
What do more complex robots require?
More complex planning
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
What are some applications that might want to cover space?
Vacuum cleaners
Lawn mowers
Harvesting
etc
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
What is a PSPACE problem?
A class of problems that can be solved in poly space
(same as P problems but for space)
What is a PSPACE hard problem?
At least as difficult as the hardest problems in PSPACE
What is a PSPACE-complete algorithm?
The hardest problems in PSPACE
What is a complete algorithm?
An algorithm that always finds a solution in finite time if it exists, or returns no solution
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
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
What are bug algorithms roughly inspired by?
Insect capabilities
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?
- Initialise goal with 0 and all other cells with infinity
- Push goal on ‘open’ list
- Pop cell from ‘open’ list and calculate the values of its neighbours
- If value of neighbour lower than previously stored, update to new value and push neighbour on the list
- 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
