Brainscape's Knowledge GenomeTM

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


See full index

COMP 417 Intro to Robotics and Intelligent Systems > Midterm 1: Week 1 to 6 > Flashcards

Midterm 1: Week 1 to 6 Flashcards

1
Q

What is an intelligent robot?

A

Intelligent robots are devices made of hardware and software.

The primary structure of intelligence in a robot is the sense-plan-act loop that allows reaction to the surrounding world.

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

Sense-plan-act loop

A

Sense: Gather information

Plan: Take the information and come up with a series of behaviours to do something

Act: perform the plan

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

State Space

A

Set of all physical situations that could arise. It captures the meaningful properties of the robot.

Notice that determining the correct representation of the state space is the #1 task of a roboticist.

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

Action Space

A

The commands, forces or other effects it can take to change its own state or that of the environment.

Notice that the action space can be state-dependent.

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

Kinematics

A

Considers constraints (limitations) on the state space and how we can transition between states.

A more formal definition is the following:

Kinematics describes the motion of points, bodies (objects), and systems of bodies (groups of objects) without considering the forces that cause them to move.

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

Dynamics

A

Consider idealized physics of motion.

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

Model

A

A function that describes a physical phenomenon or a system. Models are useful if they can predict reality up to some degree.

Mismatch between the model prediction and reality is called noise/ error

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

Omnidirectional Robots

A

Robots that can move in any direction without necessitating to rotate.

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

State of an Omnidirectional Robot

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

Control of an Omnidirectional Robot

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

Notes on Inertial frames of reference

A

G the global frame of refrence is fixe i.e. with zero velocity in our previous example.

  • If a robot’s position is known in the global frame, life is good!
    • I can correctly report its position
    • We can compute the direction and distance to a goal point
    • We can avoid collisions with obstacles also known in global frame
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Kinematics as Constraints

A

Notice that the idea of using vector spaces or set to represent everything that can happen is too broad to capture robot details.

A common form of kinematics is to state a ser of constraints also. These can be on the allowable states or how to move between states.

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

Kinematics of a simple car

State

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

Kinematics of a simple car

Control

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

Kinematics of a simple car

Velocities

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

Instantaneous Center of Rotation

A

The centre of the circle circumcises by the turning path.

Undefined for straight path segments.

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

The Dubins Car Model

A

Visualize a car that can only move forward at a constant speed s and with a maximum steering angle

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

First Robotics Theorem

A

The shortest paths of the Dubins Car can be decomposed into:

L: max left turn

R: max right turn

S; zero turn

*This rules out to ever turn partially

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

Motion Primitives

A

The fixed motion types: L, R, S, are called primitives. We can use them to decompose a series of motions to reach a goal.

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

Dubins Airplane

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

State of a Unicycle

A

Notice, here the state is the same as for the car and the omnidirectional robot since here we are just interested in the Global position of the unicycle.

x = [G_p_x, G_p_y, G__(teta)]

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

Controls of a Unicycle

A

We consider the angular vellocities on y and z.

On z it is how fast the wheel turns. On y it is how much it turns on the plane.

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

Recall that the control set of a unicycle includes the angular velocities on y and z. How do you calculate the velocities of an unicycle?

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

State of a different drive vehicle

A

Same as the car, omnidirectional robot and unicycle

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

Control of a different drive vehicle

A

In this case, we look at the velocity or turning rate of each wheel.

The turning rate of each wheel will determine the direction and force applied on the vehicle.

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

What are the velocities of this vehicle?

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

Holonomic kinematics

A

A system that constraints only on its position. That is, it has a bounded state-space, but no limits on its differential motions.

Intuition: You can immediately move in any direction you would like.

Notice that a holonomic robot can guarantee that fairly simple math can yield to optimal paths

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

Non-holonomic kinematics

A

A system that has at least one non-trivial constraint on its differential motions.

Intuition: It is possible to get someplace nearby eventually, but not in a single step.

Notice that for a non-holonomic robot we might require arbitrarily many motions to move a small distance.

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

Which of the following are non-holonomic?​

  1. A normal car
  2. A robot train that can go forward and backwards on a circular track
  3. A robot train that can only go forward on a circular track
A

1 and 3 are non-holonomic

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

Consider the Differential Drive Vehicle.

Derive the equations that represent the velocity on the right, left wheels and on the x-direction.

A

How do we find the velocity when rotating?

v = r * w where w is the angular velocity.

So, if w_D is the angular velocity, we have to find the radius.

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

In the case of a Differential Drive Vehicle, if we know the different velocities we can find the angular velocity w and the distance from the ICR to the centre fo the vehicle,

how?

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

In the case of a Differential Drive Vehicle, what happens if

v_r = v_l

A

The direction of the car would be straight.

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

In the case of a Differential Drive Vehicle, what would happen if:

v_r = -v_l

A

Then the centre of the vehicle D would be ICR.

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

In the case of the differential drive vehicle, write the equations to find the x, y position and the angle depending on the Global coordinate system.

A

G_p_x (t + 1) =

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

Forward Kinematics (fkine)

A

What is the robots state given a command/control?

Kinematics directly tell us how to compute:

  • position
  • speed on various frames
  • turning rate

All this in function of the input commands

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

Inverse Kinematics (Ikine)

A

What control(s)bring us to the desired state (if any)?

Inverse kinematics is like a “short time” plan. Depending on the form of the model, this can be easy or difficult to find.

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

When would it be easy or hard to find an inverse kinematics solution?

A

When the robot is non-holonomic it would be harder to find an inverse solution.

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

What is the motion to bring the body of a DD vehicle from (10,10,pi/4) to (0,0,0)?

A
  • Follow right angle: (10,10) - > (10.0) -> (0,0)
  • Point then Shoot: turn the car to destination and go straight line
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

Point then Shoot

A

First rotate to face the point, drive straight to the point, then rotate to goal angle

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

Robot’s Dynamic Equations

A

A robot’s dynamic equations form an equation that determines its motions in response to any possible action.

They include the geometric properties from kinematics, but also dynamic quantities: weight, motor strength, material composition, etc.

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

What does x with a dot above mean?

A

An “overdot” is a raised dot appearing above a symbol most commonly used in mathematics to indicate a derivative taken with respect to time

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

Forward Dynamics

A

Describes how an object moves in time, from initial conditions, following applies forces.

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

What is the dynamic equation of a pendulum under gravity?

A

Where:

  • I = mL^2 (inertia)
  • m = mass
  • g = gravty
  • L = length of string of the pendulum
  • teta =angle from vertical axis to inclination of string
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

Pendulum Trajectory

A

See lecture 3, recording from 48min to 54min

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

What do we have to add to the pendulum’s dynamic equation if we want it to act as a robot?

A

We have to have some way yo control it. We have to add the control.

By adding control we can now hold the pendulum stationary, build energy, reduce energy.

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

Double-Link Pendulum

A

State:

x = [teta1, teta2, teta.1, teta.2] The angle or joint 2 is expressed wrt joint 1.

Controls:

u = [torque1]

Dynamics: Slide 24 Lecture 3

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

TODO week 2 and 3

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

Name some drawbacks of Grid based planners

A
  • They work well for grids up to 3 to 4 dimensions
  • State-space discreization suggers from combinatorial explosion:
    • if x=[x_1,…., x_D] and we split each dimension into N bins then we will have N^D nodes in the graph
      • See notes on Sept. 22nd
  • This is not practical for planning paths for robot arms with multiple joints or other high-dimensional systems
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
49
Q

What do we have to do to avoid the problems that arise with the grid based planners?

A

We need to find ways to reduce the continuous domain into a sparser graph. One that covers the same space with fewer nodes and edges.

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

Cell Decomposition Planners

A

Idea:

Decompose the overall planning process into local regions.

Simple computations can tell us the path through the region.

A global computation can be performed to re-assemble the entire path, and often we can re-use our local computation for multiple queries.

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

Visibility Path

A

In this method, the objects are considered to be polygones.

  1. Draw lines of sight from the start and from the goal to all vertices of the polygones. (slide 7)
  2. Draw the lines of sight from every vertex of every obstacle (as done in 1). Remember that the lines that follow the edges of an obstalce are also considered as lines of sight.
  3. Repeat until you are done

Notice: when you add lines, the lines cannot go over an obstacle

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

Visibility Path:

Search Algorthms

A
  1. Opened vertices = {start}
  2. Repeat until done:
    1. Add edges from opened vertices to visible obstacles
    2. If goal visible from latest vertex added then done!
53
Q

Can you proof or disproof the following?

The optimal path in a 2D polygon map is the lowest cost path within the visibility graph.

A

Start with knowledge that the shortest path in free spae is a straight line. Without obstacles, we are set.

Now, consider a path that hits the obstacle anywhere other than its corner, but still passes beyond this obstacle. Can this be shorter?

Yes! If the obstacle is hit in the middle of an edge, then we have to get to one of its vertecies to turn around it, but if we directly get to a vertex, this path is shorter.

54
Q

True or False

The Visibility Graph is optimal in all dimensions.

A

False,

Visibility graphs do not preserve their optimality in higher dimensions.

See image.

55
Q

Rapidly Exploring Random Trees

A

Main Idea:

Maintain a tree of reachable configuration from the root.

Steps:

  • Sample random state
  • Find the closest state (node) already in the tree
  • Steer the closest node towards the random state
56
Q

RRT Algorithm

A
  1. V <— {x_init}; E <– empty;
  2. for i = 1, …, n do
    1. x_rand <— SampleFree_i;
    2. x_nearest <— Nearest(G = (V,E), x_rand);
    3. x_new <— Steer(x_nearest, x_rand);
    4. if ObstacleFree(x_nearest, x_new) then
      1. V <— V union {x_new}; E <— E union {(x_nearest, x_new)}
  3. return G=(V,E);
57
Q

RRT Algorithm

SampleFree()

A

SampleFree() needs to sample a random state from the uniform distribution.

How do we sample rotations uniformly?

Notice that to sample in lets say Python, you could use the rand function. If you are sampling between two values they you would have to multiply by them.

58
Q

RRT Algorithm

Nearest()

A

Nearest() searches for the nearest neighbour of a given vector. Brute force search examines |V| nodes (increasing).

Is there a more efficient method?

We will see in next lectures

59
Q

RRT Algorithm

Steer()

A

Steer() finds the controls that take the nearest state to the new state. Easy for omnidirectional robots.

What about non-holonomic systems?

In this case, you will have to consider kinematics in the Steer() function.

60
Q

RRT Algorithm

ObstacleFree()

A

ObstacleFree() checks the path from the nearest state to the new state for collisions.

How do you do collision check?

We have do check for collisions.

61
Q

Name an updside of using ObstacleFree()

A

You don’t need to model obstacles in Steer().

For example, if Steer() computes optimal controllers that we’ll learn about soon, you don’t need to model obstacles in the control computation.

62
Q

Collision Detection

A

Main idea:

When obstacles are complex, this is a problem for run-time. Bounding volume collision detection uses a simple shape for a quick check, eliminate most obstacles easily.

63
Q

Finding the Nearest Neighbour

A

Besides brute force search, there is space partitioning and locality-sensitive hashing

64
Q

Space partitioning

A

Divide the space into two and check the distance of the points. Remember in which side of the graph the point is and add to a tree.

This is called kd-trees

65
Q

Locality-sensitive Hashing

A
  • Maintain buckets
  • Similar points are placed on the same bucket
  • When searching consider only points that map to the same bucket.
66
Q

RRT Connect

A

We grow two trees, one from START and the other one from GOAL.

Each time we create a vertex, we try to greedily connect the two trees.

See example slides 28 -64

67
Q

RRT

Properties of the Planning Algorithm

A
  • The RRT will eventually cover the space i.e. it is a space-filling tree
  • The RRT will NOT compute the optimal path asymptotically
  • The RRT will exhibit “Voronoi bias”
  • The probability of RRT finding a path increases exponentially in the number of iterations
  • The distribution of RRT’s nodes is the same as the distribution in SampleFree()
68
Q

Slides 72, 73 ?

A
69
Q

Why do we bother with the problem of following a wall or a line?

A

It allows for arbitrary path following where the wall is replaced by a local line tangent to the curving path

70
Q

In control, we will add the idea of parametrized goal or reward function.

Why do we do this?

A

x = g goal

or r(x) reward

By changing the goal or setting a different reward, we can “retarget” the behaviour of our planning logic.

IMPORTANT: The goal might change over time!!!

71
Q

Double-link Inverted Pendulum

Trajectory Control

A

To get the pendulum to be in equilibrium on top of the table, the pendulum will ususally swing back and forth multiple times to gain momentum.

Why can’t we just get to the desired position in one swing?

How many swings do we need?

Once it is in balane, there has to be accurate motion and robust to disturbance to keep the balance

At this point we also start sending feedback. Motions have to correct the small errors and for this the dynamis aren’t that simple!

72
Q

Control Formulations

A

Dynamics is governed by the equations of motion of our robotic system.

dx/dt = f(x, u)

where x = pos, vel u=forces, acceleration

73
Q

Controller

A

A controller chooses u = π(x) dependent on state and time to move the system to the goal state x=g and keep it there , to follow a trajectory specied by the user (or system componenent).

The game is producing the form and details of π

π gives you control given state and dynamics.

74
Q

Underactuated

A

Depending on properties of system dynamics dx/dt = f(x,u), we might not be able to choose x directly.

75
Q

Controllable

A

We can control the system from ay initial state to any final state in a finite time.

76
Q

Control Goals

A
  • Time-respose characteristics:
    • rise/response time
    • Settling time
    • Oscillation period
  • Feasibility:
    • Given a dynamic robot and a finite set of controllers. is it possible that a controller will reach the goal?
  • Stability:
    • When you reach the goal. you will stay within a small range forever
77
Q

Control Theory Results

A
  • Important results:
    • bang-bang
    • PID
  • Probably optimal solutions under correct assumptions:
    • LQR
  • Approximations and analysis tools
    • Trajectory optimization
  • Know nothing about the model
    • Reinforcement Learning
78
Q

What does it mean to have the “best” policy?

A
  • In this case, instead of having a goal, we give a reward and we want to find the policy that optimises that reward.
    • In other words, we want to minimize a cost function that tell us how “bad” each wrong answer is.
  • This allows us to think ahead of time and solve for trajectories that minimize the sum of costs ad we formulate their matching control.
79
Q

Double Integrator

(Block on ice)

A

Goal: Move the block to some target point

WLG: assume that goal is (0,0)

The name comes from the fact that we directly influence force ~ acceleration d2x/dt2

The dynamic must be integrated twice.

80
Q

Pasive dynamics

A

Corresponds to a taxi sliding on roads. It just slides.

81
Q

Controlled Dynamics

A
82
Q

What about the controlled dynamics of a limited double integrator?

A

in this case we limit the force!

83
Q

How does the Double Integrator (DI) evolves in terms of x and dx/dt?

A

First, notice that there is no friction and that the mass of the block is 1:

84
Q

Map

A
  • A map of the environment adds external constraints on the where the robot can be
  • Maps can be given to the robot or we can build the robot with sensors
  • A map should relate to the robot’s state space
85
Q

Plan

A

Sequence of states for a robot within a map.

A plan is feasible if eahc state in the sequence and the motion netween consecutive pairs are all feasible under the kinematics and the map.

Planning algorithms can be:

  • Correct if every plan they output is feasible
  • Complete if they find a plan whenever one exists
86
Q

Planning algorithm for Dubin’s car

A

Input:

  • Map
  • current state
  • goal state

Output:

  • A plan, as a sequence of states that follow Dubins constraints, if one exists
  • A “fail” flag if not
87
Q

Full Arm Dynamics

A

Forward Dynamics:

Notice that to find the robot’s path in space you would have to integrate twice!

This is usually not done by hand. There are ODEs solvers that can help with this.

88
Q

Important Dynamics Properties

A

Stability: Does the system diverge or converge over time in a certain region?

Controllability: for all x in the state spacem is there at least one action trjectory that allows us to reach x?

Fully actuated: for all feasible acceleration directions a, does an action exist that allows us to accelerate along a?

89
Q

Controllability

A
  • A system is controllable if there exist control sequences that can bring the system from any state to any other state, in finite time
90
Q

Underactuated

A

Robot that is not able to command an instantaneous acceleration in an arbitrary direction

91
Q

Control the Robot’s motion

A

Here, planning will be concerned with kinematics and sequence states that reach a goal.

Control is oncerned with computing actions, that lead the robot along the plan or satisfy some criteria.

92
Q

Forward Kinematicks

A

What robot state results from a given control.

Input: Control

Output: State

93
Q

Inverse Kinematics

A

Which control(s) brings us to a desired state (if any)?

Input: desired state

Output: Control or sequence of controls

94
Q

Forward Dynamics

A

What robot motion will result from given forces?

Input: forces

Output: motion

95
Q

Inverse Dynamics

A

Which input force(s) will result in a desierd robot motion (if any)?

Input: desired robot motion

Output: force or sequence of forces

96
Q

Note on Inverse Kinematics and Inverse Dynamics

A

The inverse problems are more interesting, but depend on the form of the forward model.

97
Q

Single-link Cartpole

A

State:

x = [px, dpx, theta, dtheta]

State = [position and velocity, orientation and angular velocity]

Controls:

u = [f]

controls = [horizontal force applied to cart]

98
Q

Quadrotor

A

State = [roll, pitch, yaw, and roll rate, pitch rate, roll rate] wrt to G

Control = [T1, T2, T3, T4] = [Thrusts of four motors]

OR = [M1, M2, M3, M4] = [Torques of four motors]

See Lecture 3 slides 38,39

99
Q

Passive Dynamics

A

Dynamics of systems that operate without drawing (a lot of) energy from a power supply.

Usually propelled by their own weight

100
Q

Incoming data for robots

A

A robot’s sensors give it feedback on its internal state (proprioception) and allow it to observe the external world (exteroception)

Notice that sensors are not perfect.

101
Q

Sensors

A

Devices that can sense and measure physical properties of the environment.

To transmit the information, the key pheomenon is transduction.

Notice that measurements are noisy! Thus, sensors are not perfect.

102
Q

Transduction

A

Conversion of energy from form to another

103
Q

The Bug Algorithm #1

A
  1. Move in a straight line path towards G
  2. If the robot reaches G, we are done
  3. If the robot hits an obstacle, then follow the righ-hand rule and traverse its boundary
  4. Continue until the wall is no longer pointing agains the straight line from X toward G. Once this occurs, continue from Step 1
104
Q

The Bug Algorithm #1 Counter example

A
105
Q

The Bug Algorithm #2

A
  1. Move in a straight line path toward G
  2. If the robot reaches G, we are done
  3. If the robot hits an obstacle, remember the point P at which it is hit and follow the right-hand rule
  4. If the robot crosses the line PG as it walks along the wall of the obstacle, determine wheter ||X - G|| < ||P - G|| and the and the wall is not pointing against the straight line from X toward G. If both condition are satisfied, continue from step 1. Otherwise, keep walking.
  5. If P is reached again, return “No path”
106
Q

Proof the Bug #2 is complete

A
  • For each obstacle, Bug 2 will break away from it at some point if there is a path to the goal.
  • The sequence of hit points decreases in distance to the goal
  • If there is no path to the goal, then Bug 2 will terminate correctly with failure.
107
Q

What is a plan?

A

Informally:

  • Intuitively, a plan is a path from start to goal.
  • The robot should be able to follow this path under its kinetics
  • The path should not take the robot through any obstacles in the map

Formally:

  • Plan is a sequence of states: P = {x0,x1,x2,…, xn}
108
Q

What is a feasible plan?

A

A feasible plan is one where

  1. x0 = S (start)
  2. xn = G (goal)
  3. Each state xt is in free space
  4. Each transition between subsequent states, (xt, xt+1) obeys kinematics

Feasibility of states and transitions involves kinematics and maps

109
Q

Planning Algorithms

A

Planning algoriths:

Input: Start, Goal, Map, Kinematic constraints

Output: plan or “impossible”

110
Q

Planner Properties

A

Planning algorithms are:

  • Correct if every plan they output is feasible
  • Complete if they fins a plan whenever one exists
  • Terminating if they execute in a finite time

The complexity is measured by the worst-case memory and run-time in the map/robot dimensions, path length, etc.

111
Q

Planning as Graph Search

A
  • Graph nodes represent discrete states
  • Edges represent transitions/actions
  • Edges have weights

Typical assumptions:

  • Current state is known
  • Map is known
  • Map is mostly static
112
Q

How do you build your graph from a map?

A
  • Nodes are every place in space
  • Edges are drawn between neighboring places that are reachable under the kinematics
  • A path from start to goal is a list of nodes and edges
113
Q

Forward Search

A
114
Q

Dynamic Programming

A
115
Q

Dijkstra’s Algorithm

A
  • Let D(v) denote the length of the optimal path from the source node to the node v.
  • Set D(v) = infinity for all nodes except for the source node for which D(v) = 0
  • Add all nodes to Q
  • While Q is not empty
    • Get v with min cost D(v)
    • If v = goal, then done
    • For u in Ngd(v):
      • if d(u,v) + D(v) < D(u)
        • then update priority of u in priority queue Q to be d(u,v) + D(v)
116
Q

In Dynamic programming what is the Worst-case complexity?

A

O(|V|2)

117
Q

What is the downside of Dijkstra’s algorithm?

A

In a grid map, there are many nodes that are explored unecessarly. We are sure that they are not going to be part of the solution.

ex: nodes that get away from the goal.

118
Q

What is the upside of Dijkstra’s algorithm?

A

Always gives an optimal solution.

119
Q

A* Search

A

Main idea

  • modifies Dijkstra’s algorithm to be more efficient
  • Expands fewwer nodes than DIjtra’s by using a heuristic
  • While Dijkstra prioritizes nodes based on cost-to-come A* prioritizes them based on:
    • cost-to-come to v + lower bound on cost-to-go from v to v_dest
    • f(v) = g(v) + h(v)
    • f(v) is the lower bound on cost of path from source to destination that passes through v
  • Notice: this is an optimistic search since we explire the node with the smallest f(v) next.
120
Q

A* Search Algorithm

A
  1. Set g(v) = infinity for all nodes except for source g(vsrc) = 0
  2. Set h(v) = infinity for all nodes except for source f(vsrc) = h(vsrc)
  3. Add vsrc to priority queue Q with priority f(vsrc)
  4. While Q is not empty:
    1. extract v with minimum f(v) from the queue Q
    2. If found goal then done. Follow the parent pointers from v to ge the path.
    3. Remove v from queue Q
    4. explored(v) = true
    5. For u in neighborhood of v if not explored(u)”
      1. if u not in Q then
        1. Add u to Q with cost to come g(u) = g(v) + d(v,u) and priority f(u) = g(u) + h(u)
        2. Set parent of u to be v
      2. else if g(v) + d(u,v) < g(u)
        1. Update the cost-to-come and the priority of u in Q
        2. Set the parent of u to be v
121
Q

Is RRT complete?

A
  • Noticed that since it is randomized this is not obvious
  • For this we need probabilistic completeness
122
Q

Probabilistic Completeness

A

The probability that the planner returns a feasible solution, if one exists, converges to 1.0 as the number of samples tends to infinity.

123
Q

Proof or disproof:

RRT is probabilistic complete.

A

This is a straightforward consequence of the claims on the previous slide.

124
Q

What is the run-time complexity of planning from A to B with RRT?

A
  • the answer is that it is “mostly” independent of the planning dimensionality.
    • This depends on how we implement collision/free checing and nearest neighbor query independent of dimension
  • Does dependent on the “tube” surrounding feasible solutions. Essentially, how often will we randomly sample something helpful?
125
Q

Probabilistic Roadmaps (PRMs)

A
  • Notice that RRTs are good for single-query path planning
  • If you want to find the path from another A to B, you have to re-plan from scratch.
  • PRM addresses this problem.
  • It is good for multi-query path planing
126
Q

PRM Algorithm

A

Notice that to perform a query A -> B, we need to connect A and B to the PRM. We can do this by nearest neighbor search.

127
Q
A
128
Q

What is our optimal controller?

A
129
Q
A

COMP 417 Intro to Robotics and Intelligent Systems (3 decks)

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