Question 2 (1? point)

In the expected discounted reward formulation of MDPs, it would be sensible to use a discount factor of 2. True or false?

Question 2 options:

          True

          False

Question 3 (1?             point)

 

Which of the following statements accurately describe the relationship between paths and policies?

Question 3 options:

         A policy is equivalent to knowing the path from every potential state to the goal.

          Every policy has a single path as its target.

          A path is equivalent to knowing the policy at every state.

          Every path can only be the result of running a single policy.

Question 4 (1?             point)

 

Which is the best description for a Value function in Reinforcement Learning?

Question 4 options:

          The discounted reward expected at each state.

          The discounted sum of rewards expected before visiting a state.

          The discounted sum of rewards expected after visiting a state.

          The discounted sum of rewards when repeatedly visiting a state.

Question 5 (1?             point)

 

A forward kinematics routine for the 2-link arm sitting on a table (which cannot therefore reach "downwards" to prevent collision) should have which of the following outputs?

Question 5 options:

 

The joint angles [theta1, theta2] that bring the arm to its input target only.

         The joint angles [theta1, theta2] that bring the arm to its input target OR failure if no such angles are possible.

 

The end-effector [x, y, theta] OR failure if the input angles cause collision.

          The end-effector [x, y, theta] and the joint angles [theta1, theta2].

Question 6 (1?             point)

 

Consider a 6 sided dice (with numbers 1-6 written one each on the faces of a cube).

The task of the robotics algorithm is to count up the total of the numbers on the upwards faces of 2 such dice. 

What is an appropriate state-space for this task?

Question 6 options:

 

Floating point x, y, z position of the centre of each dice in 3D space.

         Integer value that discretizes roll, pitch and yaw angles into 10 bins each, placed in a 3 vector [r,p,y] for each dice.

          Integer value [1,2,3,4,5,6] encoding which side is up on each dice.

 

Floating point roll, pitch and yaw angles in 3 vector [r,p,y] for each dice.

Question 7 (1?             point)

 

Consider a 6 sided dice (with numbers 1-6 written one each on the faces of a cube).

The task of the robotics algorithm is to control a robot "dealer" who will use an arm to scoop the dice up from where they lie still on the table and pass them back to the player who will make the next roll.

What is an appropriate state-space for this task?

Question 7 options:

          Integer value [1,2,3,4,5,6] encoding which side is up on each dice.

 

Floating point roll, pitch and yaw angles in 3 vector [r,p,y] for each dice.

         Integer value that discretizes roll, pitch and yaw angles into 10 bins each, placed in a 3 vector [r,p,y] for each dice.

         Floating point x, y, z position of the centre of each dice as a 3 vector [x,y,z] in 3D space for each dice.

Question 8 (1?             point)

 

Consider a 6 sided dice (with numbers 1-6 written one each on the faces of a cube).

The task of the robotics algorithm is to perform PID control 3 fly-wheels inside the dice to control it to always land on a given number, no matter how it's rolled (e.g., 6). 

What is an appropriate state-space for this task?

Question 8 options:

 

Floating point roll, pitch and yaw angles in 3 vector [r,p,y] for each dice.

         Integer value that discretizes roll, pitch and yaw angles into 10 bins each, placed in a 3 vector [r,p,y] for each dice.

          Integer value [1,2,3,4,5,6] encoding which side is up on each dice.

 

Floating point x, y, z position of the centre of each dice in 3D space.

Question 9 (1?             point)

 

A robot's kinematics allow it to move on the (x,y) plane, always counter-clock-wise. That is instantaneously, its angular velocity around the origin can never be negative (using right-hand rule).

There are no other kinematic constraints except those written.

Question 9 options:

          The robot is holonomic

          The robot is non-holonomic

          We cannot tell from the given text

          The robot is neither holonomic nor non-holonomic

Question 10 (1?          point)

 

A robot's kinematics allow it to move freely in the (x,y) plane except for a circle of radius r surrounding the origin (0,0). There are no other kinematic constraints except those written.

Question 10 options:

          We cannot tell from the given text

          The robot is holonomic

          The robot is non-holonomic

          The robot is neither holonomic nor non-holonomic

Question 11 (1?          point)

 

An inverse kinematics routine for the 2-link arm sitting on a table (which cannot therefore reach "downwards" to prevent collision) should have which of the following outputs:

Question 11 options:

         The joint angles [theta1, theta2] that bring the arm to its input target OR failure if no such angles are possible.

 

The joint angles [theta1, theta2] that bring the arm to its input target only.

          The end-effector [x, y, theta] and the joint angles [theta1,theta2].

 

The end-effector [x, y, theta] OR failure if the input angles cause collision.

Question 12 (1?          point)

 

Suppose we replace the random point generator to select xrand in the RRT algorithm with always selecting exactly the goal point (xrand = xgoal) for each iteration of building the tree. 

The resulting algorithm still be probabilistically complete. True or false?

Question 12 options:

          True

          False

Question 13 (1?          point)

 

Suppose a planning graph has both positive and negative edge weights. How does this affect Dijkstra's method (assuming it is applied exactly as-is to the graph, and no transformations/fixes are applied). 

Question 13 options:

          It will terminate, but the path will not necessarily be shortest.

          It will terminate with the optimal path always.

          It will become stuck in negative weight cycles and never terminate.

          It will never pop any node off the priority queue.

Question 14 (1?          point)

 

Suppose a robot map has two independent components, separated by a complete wall, such that there is no way to pass from one to the other (no feasible plan exists).

What guarantees do we have from a CORRECT planning method when run on this situation?

Question 14 options:

          The CORRECT property does not directly apply to this situation.

          It is guaranteed to return a path.

          It is guaranteed to return a feasible path.

          It is guaranteed to return in a finite number of iterations.

Question 15 (1?          point)

 

Suppose a robot map has two independent components, separated by a complete wall, such that there is no way to pass from one to the other (no feasible plan exists).

What guarantees do we have from a COMPLETE planning method when run on this situation?

Question 15 options:

          It is guaranteed to return a feasible path.

          It is guaranteed to return a path.

          It is guaranteed to return in a finite number of iterations.

          The COMPLETE property does not directly apply to this situation.

Question 16 (1?          point)

 

Suppose a planning graph has both positive and negative edge weights. How does this affect the A* planning method, using straight-line distance as a heuristic (assuming it is applied exactly as-is to the graph, and no transformations/fixes are applied). 

Question 16 options:

          It will terminate, but the path will not necessarily be shortest.

          It will never pop any node off the priority queue.

          It will become stuck in negative weight cycles and never terminate.

          It will terminate with the optimal path always.

Question 17 (1?          point)

 

Suppose a robot map has two independent components, separated by a complete wall, such that there is no way to pass from one to the other (no feasible plan exists).

What guarantees do we have from a TERMINATING planning method when run on this situation?

Question 17 options:

          It is guaranteed to return in a finite number of iterations.

          The TERMINATING property does not directly apply to this situation.

          It is guaranteed to return a feasible path.

          It is guaranteed to return a path.

Question 18 (1?          point)

 

When applying the Occupancy Grid mapping algorithm for 100 scans, using a Lidar that takes 100 points for each scan, which of the following is an accurate description of how points and scans are integrated to build a map?

Question 18 options:

          All 10,000 points must be integrated at the same instant

         All 100 points in each scan must be integrated at the same instant, but the scans can be integrated individually. 

          Every single point can be integrated individually.

         The i'th point of each scan (100 points) must be integrated at the same moment, but each "i" can be integrated individually.

Question 19 (1?          point)

 

Which of the following is theoretically able to achieve the highest precision in representing the geometry of a map?

Question 19 options:

          A quad-tree with 10,000 leaf nodes

          A polygon with 10,000 faces

          An occupancy grid with 10,000 cells

          A signed distance function

Question 20 (1?          point)

 

In the oct-tree representation of space, in which cases would you decomposes a cell further?

Question 20 options:

          Only when it is entirely free.

          Only when it is entirely occupied.

          If it is either entirely occupied or entirely free.

          If it is partially occupied and partially free.

Question 21 (1?          point)

 

When re-sampling in a particle filter, the proximity of particles (their density) determines how frequently each old particle will be selected to re-sample in the new set. True or false?

Question 21 options:

          True

          False

Question 22 (1?          point)

 

Suppose we have a target probability distribution p( a | b, c, ... , y, z ) and would like to deal with the complexity of conditioning on the 25 variables (b through z).

Which of these tools are most likely to be the *first* step in this process? 

Question 22 options:

          Apply the Law of Total Probability

          Use a sampling-based representation (particles)

          Apply Conditional Bayes' Rule

          Take the log likelihood

Question 23 (1?          point)

 

Iterative Closest Points is typically a sub-step of Particle Filtering. True or false?

Question 23 options:

          True

          False

Question 24 (1?          point)

 

In the quad-tree representation of space, in which cases would you decomposes a cell further?

Question 24 options:

          If it is either entirely occupied or entirely free.

          Only when it is entirely free.

          Only when it is entirely occupied.

          If it is partially occupied and partially free.

Question 25 (1?          point)

 

Which choice best describes the guaranteed optimality of the gain matrix, K solved for in the infinite-horizon LQR derivation?

Question 25 options:

          It is optimal only near the goal state, g, 

          It computes the optimal control for all states at time t only.

          The gain matrices are the same at all times.

          It is a greedy optimizer to maximize reward at time t alone.

 

 

Question 28

?

(1

point

)

 

 

A phase plot diagram graphs the robot's velocity on the vertical axis vs the robot's position on the horizontal axis. For a certain robot, the passive dynamics are such that it's phase plot has horizontal arrows to the right in the entire upper half (this was true for the un-damped block-on-ice). 

Describe the control procedure that would produce a controlled-dynamics phase plot with the horizontal arrows pointing instead to the left in the entire upper half.

Question 28 options:

         The controller should apply a force in the negative direction larger than the system's momentum (mass times velocity).

          This is physically impossible given the nature of the phase plot.

         The controller should apply a force in the positive direction larger than the system's momentum (mass times velocity).

         We can achieve the reversal only in the upper-right quadrant, by giving a force in the negative direction.

Question 29 (1?          point)

 

LQR is a control solution based on the Bellman Equation. True or false?

Question 29 options:

          True

          False

Question 30 (1?          point)

 

The optimal bang-bang controller for the block-on-ice causes the robot to oscillate. True or false?

Question 30 options:

          True

False

 

 

Written Response Questions

 

 

 

 

Question 33 (4?          points)

 

Consider pseudo-code for a planning algorithm:

function RapidlyExploringRandomSnake(start,goal): 

0. Set the variable xlast = start While True:
1. Sample xrand uniformly in the configuration space.
2. Steer from xlast towards xrand. If this succeeds, define variable xnew. Else continue.
3. Add an edge xlast -> xnew 
4. Update variable xlast = xnew

     If xlast is within radius epsilon of goal:

          Break the while loop

End While

Return xlast  # User can reconstruct the path by following edges backwards

End function

Is the RapidlyExploringRandomSnake (RRS) planner probabilistically complete? If yes, try to prove it. If no, give a counter-example or counter-proof.

Full point solutions should make comparison to RRT in the argument, and include a diagram of the "snake" plan that illustrates aspects of what the text describes. Recommended method for completing this question is a typed solution (MS-Word, Emacs, etc) with the diagram embedded in the PDF.

Question 34 (4?          points)

 

The following diagram shows one particle out of a particle filter in 2D, which is sensing 4 landmarks with a range finder:

 

 

 

Question 35 (8?          points)

 

Design Essay Question: Apply COMP 417 Ideas for the SpaceX Starship launch vehicle

 

The vehicle shown above, SpaceX's Starship, was launched yesterday and exploded in a giant fireball trying to land (only robots were damaged, no humans affected). It may be that the designers had sadly not taken COMP 417, and therefore your job is to apply as many of the COMP 417 topics as you're able to describe how to do the critical task:

How can Starship land safely, arriving on the launch pad at exactly the right position, velocity, angle, etc?

Structure your answer as follows:

• A diagram showing your statespace, action-space, and any goals, paths, or estimator elements used for algorithms you mentioned. 
• 1 paragraph to INTRODUCE your overall idea, and start from the basics we used in every problem in 417: explain the states and actions. For Starship, this means defining what sensors and actuators (rocket thrusters) you'll consider and how they can be modeled (kinematics, dynamics, sensing error, etc). You don't have to be realistic to the actual vehicle. Just invent some setup you see fit (but it can be interesting to explain the real vehicle if you know about it, or explain how your setup is ideal/better). Do ensure to mention the geometric as well as probability models associated with each element.
• 3 short paragraphs labeled with COURSE CONCEPTS, briefly explaining how you'd apply them. List the critical equations involved and make them specific to this problem. State important analysis for each to determine if the Starship will crash or not (state how to make it safe). Ensure to tie back to your defined states, actions, and models.