Comp Robotics Exam 2

What is the motivation for sampling-based motion planning?

It avoids constructing the entire configuration space by randomly sampling configurations and connecting them, making planning practical in high-dimensional spaces.

What are the main steps of PRM?

Sample collision-free configurations, connect nearby samples using a local planner, collision-check connections, and search the roadmap for a path.

What are the main steps of RRT?

Start a tree at the initial configuration, sample a random configuration, find the nearest tree node, extend toward the sample, collision-check, and repeat until reaching the goal.

When should PRM be used instead of RRT?

PRM builds a reusable roadmap for multiple queries, while RRT grows a tree for a single start-to-goal query.

What is Voronoi bias in RRT?

Nodes with larger Voronoi regions are more likely to be selected as nearest neighbors, causing RRT to explore unexplored areas.

How does bidirectional RRT work?

Grow two trees, one from the start and one from the goal, and attempt to connect them through a collision-free path.

What modules must be specified for PRM?

Sampling method, distance metric, neighborhood selection, local planner, and collision checker.

What choices were used in the original PRM implementation?

A typical early PRM uses random collision-free samples, nearby-neighbor connections, simple local interpolation, a configuration-space distance metric, and collision checking. Check lecture notes for the precise original implementation.

How do we sample uniformly in SE(2)?

Sample x and y uniformly within bounds and sample orientation theta uniformly between 0 and 2π.

How do we sample uniformly in SE(3)?

Sample translation coordinates within bounds and independently sample a uniform 3D rotation, commonly using unit quaternions. Uniform Euler angles are not sufficient.

What are common representations of 3D rotations?

Euler angles use three parameters but have singularities; rotation matrices avoid singularities but use nine entries; unit quaternions are compact and avoid gimbal lock but have a unit-length constraint.

How can distance be defined in SE(2)?

Combine Euclidean translation distance with the shortest wrapped angular difference, using an appropriate weighting factor.

How is distance defined in S1 and T2?

In S1, use the shortest angular difference. In T2, combine the shortest wrapped angular differences for both coordinates.

What is the shortest path between rotations in SO(3)?

A geodesic corresponding to rotation around a fixed axis through the minimum rotation angle, often computed using quaternion SLERP.

Why is a kd-tree useful in motion planning?

It speeds up nearest-neighbor and neighborhood searches by organizing sampled configurations into a spatial search tree.

How does a kd-tree work?

It recursively partitions points using axis-aligned splits, allowing searches to eliminate regions that cannot contain better matches.

How do you construct a balanced kd-tree?

Choose a splitting axis, split points at the median, and recursively repeat for each subset.

How does nearest-neighbor search in a kd-tree work?

Follow the branch containing the query, track the closest point, and backtrack when other regions could contain a closer point.

What is a Bounding Volume Hierarchy (BVH)?

A hierarchy of bounding shapes used to quickly eliminate groups of objects that cannot collide before performing detailed collision tests.

What is an Oriented Bounding Box (OBB)?

A bounding box that can rotate to align with an object, often fitting it more tightly than an axis-aligned box.

What does the Separating Axis Theorem state?

Two convex objects are separate if some axis exists where their projections do not overlap.

What is sample dispersion?

The maximum distance from any point in the space to its nearest sample. Lower dispersion means better coverage.

Why is sample dispersion useful?

It measures how well samples cover a space and helps identify large unsampled regions.

Why use quasi-random sampling?

Low-discrepancy samples provide more even coverage and fewer large gaps than ordinary random samples.

What property do original PRM and RRT provide?

Probabilistic completeness under suitable assumptions.

What is probabilistic completeness?

If a sufficiently robust feasible path exists, the probability of failing to find it approaches zero as the number of samples increases.

When do sampling-based planners perform well?

In open environments with wide passages because collision-free configurations and connections are relatively easy to find.

When do sampling-based planners struggle?

In narrow passages, cluttered environments, and constrained regions where useful samples are difficult to obtain.

What is Obstacle-Based PRM (OBPRM)?

A variation of PRM that samples near obstacle boundaries to improve coverage of difficult regions such as narrow passages.

What is asymptotic optimality?

As the number of samples increases toward infinity, the best solution cost converges to the globally optimal cost with probability one under suitable assumptions.

Are standard RRT paths optimal?

No. Standard RRT finds feasible paths but does not guarantee optimality, and paths can be long or jagged.

What are the main steps of RRT*?

Sample, find the nearest node, steer, find nearby nodes, choose the lowest-cost feasible parent, insert the new node, and rewire neighbors to reduce costs.

How does PRM* differ from PRM?

PRM* uses a theoretically appropriate connection radius or number of neighbors that scales with the number of samples to achieve asymptotic optimality.

How does one iteration of RRT* differ from RRT?

RRT connects to the nearest node, while RRT* selects the lowest-cost feasible parent among neighbors and rewires existing nodes when beneficial.

What is the pseudocode for RRT*?

Initialize the tree; repeatedly sample, find nearest, steer, collision-check, find neighbors, choose minimum-cost feasible parent, insert, and rewire; return the best goal-reaching path.

What is the main idea of potential functions?

Use an artificial potential that attracts the robot toward the goal and repels it from obstacles. Motion follows the negative gradient.

What is a common attractive potential?

Uatt(q) = (k/2)||q - qgoal||². The negative gradient points toward the goal.

What is a common repulsive potential?

A potential that increases as obstacle distance decreases, commonly active only within a chosen obstacle influence distance.

Why can potential fields get stuck?

Attractive and repulsive forces can cancel at a local minimum that is not the goal.

Give an example of a local minimum in potential fields.

A robot moving toward a goal behind a U-shaped obstacle becomes trapped when attractive and repulsive forces balance.

What is the control law for a potential field?

Compute the potential gradient and move in the negative gradient direction, such as qdot = -k∇U(q), subject to motion constraints.

What is a navigation function?

A specially constructed smooth potential with a unique minimum at the goal and no other local minima in free space under appropriate assumptions.

How does path optimization work?

Begin with an initial path and iteratively modify it to reduce costs such as length, smoothness, or obstacle proximity while satisfying constraints.

How are path optimization and potential fields similar?

Both use cost or potential gradients. Potential fields typically guide a configuration, while path optimization modifies an entire path.

What are the advantages of path optimization?

It can produce shorter, smoother, and dynamically feasible paths and incorporate multiple planning constraints.

What is the main disadvantage of path optimization?

It can become trapped in local minima and often depends heavily on the initial path.

How can path optimization be combined with probabilistic completeness?

First use a probabilistically complete sampling-based planner to find a feasible path, then optimize the resulting path.

What is a homotopy class?

A group of paths that can be continuously deformed into each other without crossing obstacles while keeping endpoints fixed.

How do homotopy classes affect path optimization?

Local optimization usually stays within its current homotopy class and may miss better paths that travel around obstacles differently.

What is the difference between a path and a trajectory?

A path describes geometric motion without timing, while a trajectory describes configuration as a function of time, including speed and acceleration.

What is a fully actuated system?

A system with enough independent control inputs to directly control all independent degrees of freedom, subject to its dynamics.

What is an underactuated system?

A system with fewer independent control inputs than degrees of freedom, meaning some motions cannot be controlled directly.

What is the Lagrange function?

L = T - V, where T is kinetic energy and V is potential energy.

What is the general form of robot dynamics?

M(q)qddot + C(q,qdot)qdot + g(q) = B(q)u, where M is inertia, C contains velocity effects, g is gravity, and u is control input.

What is decoupled trajectory planning?

First compute a geometric path, then determine how to traverse it over time while respecting dynamic and actuator constraints.

What is the advantage of decoupled trajectory planning?

It separates geometric planning from timing, simplifying the problem and allowing different feasible speed profiles along the same path.

What phase space is used in path time scaling?

The phase plane contains path position s on the horizontal axis and path speed sdot on the vertical axis.

How are feasible accelerations shown in the phase plane?

At each state (s,sdot), acceleration must satisfy L(s,sdot) ≤ sddot ≤ U(s,sdot).

What is bang-bang control?

A time-optimal control strategy that switches between extreme feasible control values, often maximum acceleration and maximum braking.

What are inadmissible regions in the phase plane?

States that violate dynamic or actuator constraints, including states with no feasible acceleration because L > U.

What are inevitably inadmissible states?

States that may currently satisfy constraints but cannot reach the required terminal state without eventually violating constraints.

What assumptions are made by the time-scaling algorithm?

The path is fixed and sufficiently smooth, acceleration bounds can be computed, and feasible speeds at each path position are assumed to range from zero to a maximum.

What are the five high-level steps of the time-scaling algorithm?

Construct the admissible region, calculate acceleration bounds and limiting curves, integrate acceleration and braking profiles, identify switching or tangent points, and connect feasible pieces.

How do you interpret a phase-plane trajectory?

Moving right means advancing along the path, rising means increasing speed, and falling means braking.

What is the maximum-velocity curve?

The boundary describing the highest allowable speed at each path position under dynamic constraints.

What does it mean if a backward curve from the goal reaches sdot = 0 at s < 1?

The backward-integrated curve reaches zero speed before the endpoint of the path and cannot alone connect the specified start and goal conditions.

What is the objective of path time scaling?

Find the fastest feasible timing along a fixed geometric path while satisfying velocity, acceleration, and control limits.

What is timing many paths using branch and bound?

Compare candidate geometric paths using lower bounds on traversal time and avoid fully evaluating candidates that cannot outperform the best known solution.

When can branch and bound prune a path?

When a valid lower bound on its traversal time is at least as large as the time of the best known feasible solution.

What does an AVP-RRT node store?

A reachable interval of path velocities representing all feasible speeds that can reach that node along its tree path.

How does AVP-RRT propagate a velocity interval?

It propagates feasible incoming speeds along the candidate path segment using dynamic acceleration bounds to compute an outgoing speed interval.

When does AVP-RRT reject an extension?

When the reachable outgoing velocity interval is empty, meaning no feasible timing exists along that extension.

Why does AVP-RRT store a velocity interval instead of one speed?

It preserves multiple possible reachable speeds and provides more flexibility when extending the tree.

How does a sharp bend affect time-optimal timing?

The robot brakes before the bend, passes through at a constrained lower speed, and accelerates afterward when feasible.

What are acceleration, braking, and switching pieces?

Acceleration follows the upper acceleration bound, braking follows the lower bound, and switching points connect different control pieces.

What is a zero-inertia point?

A point where the coefficient of path acceleration in a dynamic constraint becomes zero, so changing path acceleration cannot affect that constraint at that point.

How can a zero-inertia point impose a speed limit?

The affected constraint may depend on speed even when its acceleration coefficient is zero, creating a maximum feasible speed.

What is the feasible-speed interval assumption?

At every path position, feasible speeds are assumed to form a continuous interval from zero to a maximum allowable speed.

How can gravity violate the feasible-speed interval assumption?

A robot may lack sufficient static torque to resist gravity at low speed, while faster motion creates inertial effects that make the motion feasible.

What does the forward maximum-acceleration sweep do?

It starts at the initial state and follows the maximum feasible acceleration to construct a fast forward phase-plane profile.

What does the backward maximum-braking sweep do?

It integrates backward from the goal using maximum feasible braking to determine which states can reach the required terminal speed.

What does an intersection of forward and backward sweeps mean?

It can indicate a switching point from acceleration to braking that allows the initial and terminal conditions to be connected.

What happens if the forward and backward sweeps cannot connect?

Their direct combination is not a feasible complete timing. Additional switching or boundary segments may be necessary, or the path may be infeasible.

What does L = U mean in the phase plane?

The lower and upper acceleration limits coincide, leaving exactly one feasible acceleration at that state.

What is a tangent point on the speed-limit curve?

A state where a feasible phase trajectory has the same slope as the speed-limit boundary.

How are tangent points used in time-optimal timing?

They help identify transitions between maximum-acceleration, maximum-braking, and speed-limit-constrained portions of a trajectory.