Title: Revision / Robotics / Robotics
On every note of this deck, unless a note says otherwise:
title: robotics

Q: * Robotics — COMP3631
** The Robotics Pipeline
*** The robotics pipeline order [...]
A: spatial transformations → FK → IK → trajectory generation → feedback control → path planning → localisation
title: robotics

Front: * Robotics — COMP3631
** The Robotics Pipeline
*** Robotics pipeline overview
Back: Spatial Transformations  (ATB — where is frame B in frame A?)
              ↓
  Forward Kinematics       (joint angles θ → end-effector pose)
              ↓
  Inverse Kinematics       (desired pose → joint angles θ)
              ↓
  Trajectory Generation   (waypoints → smooth θ(t) over time)
              ↓
  Feedback Control        (track θ_desired(t) against θ_actual(t))
              ↓
  Path Planning           (collision-free path in workspace)
              ↓
  Localisation            (where is the robot in its environment?)

Front: * Robotics — COMP3631
** Spatial Transformations
*** What does a transformation matrix \(^AT_B\) encode?
Back: the pose (position + orientation) of frame B expressed in frame A

Q: * Robotics — COMP3631
** Spatial Transformations
*** \(^AT_B\) column layout::
-col 1: [...]
-col 2: [...]
-col 3: [...]
A: X-axis of B represented in A; Y-axis of B represented in A; origin of B (translation) represented in A
title: robotics

Front: * Robotics — COMP3631
** Spatial Transformations
*** Converting a point from frame B to frame A
Back: \[{}^A p = {}^AT_B \cdot {}^Bp\]

Front: * Robotics — COMP3631
** Spatial Transformations
*** What is a homogeneous coordinate?
Back: appending a 1 to a 2D/3D point so a single matrix multiplication handles both rotation and translation

Front: * Robotics — COMP3631
** Spatial Transformations
*** 2D transformation matrix (rotation by \(\theta\), translation to \([{}^Ax_B,\; {}^Ay_B]\))
Back: \[{}^AT_B = \begin{pmatrix} \cos\theta & -\sin\theta & {}^Ax_B \\ \sin\theta & \cos\theta & {}^Ay_B \\ 0 & 0 & 1 \end{pmatrix}\]

Front: * Robotics — COMP3631
** Spatial Transformations
*** Inverse transformation \({}^BT_A\)
Back: \(({}^AT_B)^{-1}\) — converts points from frame A to frame B

Front: * Robotics — COMP3631
** Spatial Transformations
*** Chain rule for transformation matrices — given \({}^WT_R\), \({}^WT_C\), \({}^CT_O\), find \({}^RT_O\)
Back: \[{}^RT_O = {}^RT_W \cdot {}^WT_C \cdot {}^CT_O = ({}^WT_R)^{-1} \cdot {}^WT_C \cdot {}^CT_O\]

Front: * Robotics — COMP3631
** Spatial Transformations
*** 3D transformation matrix size
Back: \(4 \times 4\) (vs \(3 \times 3\) in 2D; extra row/column for homogeneous coordinates)

Front: * Robotics — COMP3631
** Forward Kinematics
*** Forward kinematics problem
Back: given joint angles \(\theta_1\ldots\theta_N\), compute the end-effector pose \({}^BT_H\)

Front: * Robotics — COMP3631
** Forward Kinematics
*** FK chain rule for N-link arm
Back: \[{}^BT_H = {}^BT_{L_1} \cdot {}^{L_1}T_{L_2} \cdot \ldots \cdot {}^{L_N}T_H\]

Front: * Robotics — COMP3631
** Forward Kinematics
*** Why attach a coordinate frame to each link?
Back: so the transformation between adjacent links is a pure function of that joint's angle only

Front: * Robotics — COMP3631
** Forward Kinematics
*** 2-link planar arm — end-effector \(x\) position
Back: \[x = l_1\cos\theta_1 + l_2\cos(\theta_1+\theta_2)\]

Front: * Robotics — COMP3631
** Forward Kinematics
*** 2-link planar arm — end-effector \(y\) position
Back: \[y = l_1\sin\theta_1 + l_2\sin(\theta_1+\theta_2)\]

Front: * Robotics — COMP3631
** Inverse Kinematics
*** Inverse kinematics problem
Back: given a desired end-effector pose \({}^BT_H\), find joint angles \(\theta_1\ldots\theta_N\)

Front: * Robotics — COMP3631
** Inverse Kinematics
*** When does IK have no solution?
Back: the target pose is outside the robot's reachable workspace

Front: * Robotics — COMP3631
** Inverse Kinematics
*** Workspace of a 1-link arm
Back: a circle of radius \(l\)

Q: * Robotics — COMP3631
** Inverse Kinematics
*** Workspace of a 2-link arm::
-outer radius: [...]
-inner radius: [...]
A: \(l_1 + l_2\); \(|l_1 - l_2|\)
title: robotics

Front: * Robotics — COMP3631
** Inverse Kinematics
*** When does IK have multiple solutions?
Back: the arm is redundant — the target is reachable in more than one joint configuration

Front: * Robotics — COMP3631
** Inverse Kinematics
*** IK via Gradient Descent
**** IK as an optimisation problem — objective function
Back: \[g(\theta) = \bigl(f(\theta) - p^*\bigr)^T\!\bigl(f(\theta) - p^*\bigr)\] minimises the squared distance between FK result and desired position \(p^*\)

Front: * Robotics — COMP3631
** Inverse Kinematics
*** IK via Gradient Descent
**** Gradient descent update rule
Back: \[\theta \leftarrow \theta - \alpha \cdot \nabla g(\theta)\] where \(\alpha\) is the learning rate

Front: * Robotics — COMP3631
** Inverse Kinematics
*** IK via Gradient Descent
**** Limitation of gradient descent for IK
Back: may converge to a local minimum, not the global optimum

Front: * Robotics — COMP3631
** Inverse Kinematics
*** IK via kNN
**** How to collect training data for kNN IK?
Back: sample random joint angles \(\theta\); apply FK to get end-effector positions; store (position, \(\theta\)) pairs

Front: * Robotics — COMP3631
** Inverse Kinematics
*** IK via kNN
**** kNN IK prediction
Back: find \(k\) nearest positions in the dataset; return weighted average of their joint angles

Front: * Robotics — COMP3631
** Inverse Kinematics
*** IK via kNN
**** kNN weighting — why inversely proportional to distance?
Back: closer neighbours are more relevant to the query point

Q: * Robotics — COMP3631
** Inverse Kinematics
*** IK via kNN
**** Limitations of kNN IK::
-[...]
-[...]
-[...]
A: sensitive to the choice of \(k\); poor performance in high dimensions (curse of dimensionality); depends on a good distance metric
title: robotics

Q: * Robotics — COMP3631
** Trajectory Generation
*** Two spaces for trajectory planning::
-Cartesian space: [...]
-Joint space: [...]
A: plan end-effector position over time; plan joint angles over time
title: robotics

Front: * Robotics — COMP3631
** Trajectory Generation
*** Joint-space trajectory workflow
Back: run IK on each waypoint to get joint angles; interpolate joint angles smoothly over time

Front: * Robotics — COMP3631
** Trajectory Generation
*** What does the robot actually execute?
Back: a discrete sequence of joint angles at the servo rate

Front: * Robotics — COMP3631
** Trajectory Generation
*** If planned in Cartesian space, what extra step is needed?
Back: apply IK at each time step to convert Cartesian positions to joint angles

Front: * Robotics — COMP3631
** Trajectory Generation
*** Linear trajectory formula
Back: \[p(t) = p_0 + (g - p_0) \cdot \frac{t}{T}\]

Front: * Robotics — COMP3631
** Trajectory Generation
*** Why use polynomial trajectories?
Back: to simultaneously satisfy position and velocity constraints at start, via-points, and end

Front: * Robotics — COMP3631
** Trajectory Generation
*** Second-order polynomial — coefficients and constraints
Back: 3 coefficients; needs 3 conditions (e.g. position at \(t=0\), \(t=T\), and one via-point)

Front: * Robotics — COMP3631
** Trajectory Generation
*** Fifth-order polynomial — why needed?
Back: 6 boundary conditions (position + velocity at start, via-point, end) require 6 coefficients

Front: * Robotics — COMP3631
** Feedback Control
*** Open-loop control
Back: fixed command sent with no correction based on actual output

Front: * Robotics — COMP3631
** Feedback Control
*** Why open-loop control fails
Back: motor/ground imperfections cause the robot to deviate; errors accumulate and cannot be corrected

Front: * Robotics — COMP3631
** Feedback Control
*** P-control (proportional) velocity law
Back: \[v(t) = k \cdot (g - x(t)), \quad k > 0\]

Front: * Robotics — COMP3631
** Feedback Control
*** Why does P-control converge to goal?
Back: when \(x < g\), velocity is positive (drives toward goal); when \(x > g\), velocity is negative (corrects overshoot); error decays exponentially

Front: * Robotics — COMP3631
** Feedback Control
*** Tracking error
Back: difference between the desired trajectory value and the actual value at time \(t\)

Front: * Robotics — COMP3631
** Feedback Control
*** P-control for joint tracking
Back: \[\omega(t) = k \cdot \bigl(\theta_\text{desired}(t) - \theta_\text{actual}(t)\bigr)\]

Front: * Robotics — COMP3631
** Feedback Control
*** Why use PD control in practice?
Back: the D (derivative) term damps oscillation and overshooting, improving stability compared to P alone

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Potential Field Method
**** Total force on robot in potential field
Back: \[F(q) = -\nabla U(q) = F_\text{att} + F_\text{rep}\]

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Potential Field Method
**** Attractive potential formula
Back: \[U_\text{att}(q) = \tfrac{1}{2}\, k_\text{att}\, \rho_\text{goal}^2(q)\] where \(\rho_\text{goal}\) is the distance to the goal

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Potential Field Method
**** Repulsive potential — when does it activate?
Back: only within distance \(\rho_0\) of the nearest obstacle; goes to \(\infty\) as distance \(\to 0\)

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Potential Field Method
**** Potential field advantage
Back: requires only local information — no global map needed

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Potential Field Method
**** Potential field limitation
Back: robot can get stuck at a local minimum where \(F_\text{att} = -F_\text{rep}\)

* Robotics — COMP3631
** Path Planning for Mobile Robots
*** Cell Decomposition Methods
**** Fixed-size cell decomposition — steps::
-1: overlay uniform grid on workspace
-2: mark any cell even partially occupied as blocked
-3: graph search (e.g. Dijkstra or A*) over free cells from start to goal
-4: connect cell midpoints to form the robot path
title: robotics

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Cell Decomposition Methods
**** Fixed-size limitation — completeness
Back: not complete; coarse cells can block narrow passages that actually exist

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Cell Decomposition Methods
**** Adaptive-size cell decomposition — improvement
Back: subdivides cells near obstacles to a finer threshold; can navigate narrow passages

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Cell Decomposition Methods
**** Adaptive-size limitation
Back: may still lose very narrow passages at threshold; harder to implement

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Cell Decomposition Methods
**** Exact cell decomposition — how cells are created
Back: scan along one axis; split at every obstacle corner to create convex cells

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Cell Decomposition Methods
**** Why must cells be convex?
Back: any two points inside a convex cell can be joined by a collision-free straight line

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Cell Decomposition Methods
**** Exact cell decomposition — completeness
Back: complete

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Cell Decomposition Methods
**** Planner completeness definition
Back: finds a solution whenever one exists

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Cell Decomposition Methods
**** Cell decomposition comparison
Back: Method | Complete? | Narrow passages | Implementation
Fixed-size grid | No | Blocked by coarse cells | Easy
Adaptive (quadtree) | No (close) | Better (finer cells near obstacles) | Harder
Exact decomposition | Yes | Handles correctly (convex cells) | Difficult

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Configuration Space
**** Robot configuration definition
Back: complete specification of the position of every point on the robot

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Configuration Space
**** Configuration space (C-space) definition
Back: the space of all possible configurations of the robot

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Configuration Space
**** C-space dimension for a translating-only robot
Back: 2 (\(x\), \(y\))

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Configuration Space
**** C-space dimension for a translating + rotating robot
Back: 3 (\(x\), \(y\), \(\theta\))

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Configuration Space
**** C-space dimension for a robot arm with \(d\) joints
Back: \(d\)

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Configuration Space
**** Obstacle inflation for a circular mobile robot
Back: inflate each obstacle by the robot's radius; then plan for the robot's centre as a point robot

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Configuration Space
**** Why obstacle inflation works
Back: the inflated obstacle accounts for the robot's body; treating the robot as a point is then exact

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Configuration Space
**** Why cell decomposition is intractable for high-DoF arms
Back: building C-space obstacles requires \(n^d\) collision checks (e.g. \(360^7 \approx 2 \times 10^{18}\) for a 7-DoF arm at 1° resolution)

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Sampling-Based Planning
**** Probabilistic Roadmap (PRM) — key idea
Back: randomly sample collision-free configurations; connect nearby ones to build a reusable roadmap graph; search graph for a path

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Sampling-Based Planning
**** Rapidly-Exploring Random Tree (RRT) — key idea
Back: grow a tree from the start by sampling random configs and extending toward them; periodically bias toward the goal

* Robotics — COMP3631
** Path Planning for Mobile Robots
*** Sampling-Based Planning
**** RRT algorithm::
-1: set start as root
-2: sample \(q_\text{rand}\) (use goal every few iterations)
-3: find nearest tree node \(q_\text{near}\)
-4: step from \(q_\text{near}\) toward \(q_\text{rand}\); stop if collision
-5: repeat until goal is in tree
-6: trace from goal to root for path
title: robotics

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Sampling-Based Planning
**** PRM vs RRT — key difference
Back: PRM builds a reusable multi-query roadmap; RRT builds a single-query tree guided toward the goal

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Sampling-Based Planning
**** Sampling advantage over cell decomposition
Back: no explicit C-space obstacle representation — only collision-check at sampled points

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Sampling-Based Planning
**** RRT/PRM completeness
Back: probabilistically complete (probability of finding a solution → 1 as samples → ∞)

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Sampling-Based Planning
**** RRT weakness
Back: paths are not optimal; can appear random/jerky

Front: * Robotics — COMP3631
** Path Planning for Mobile Robots
*** Sampling-Based Planning
**** PRM vs RRT comparison
Back: | PRM | RRT
Query type | Multi-query (roadmap reused) | Single-query (tree rebuilt each time)
Goal bias | None during construction | Periodically samples toward goal
Best for | Same environment, many queries | Single path; dynamic environments
Path quality | Depends on connection radius | Non-optimal; jerky
Completeness | Probabilistically complete | Probabilistically complete

Front: * Robotics — COMP3631
** Bayes' Rule
*** Bayes' rule
Back: \[P(A \mid B) = \frac{P(B \mid A) \cdot P(A)}{P(B)}\]

Q: * Robotics — COMP3631
** Bayes' Rule
*** Posterior, likelihood, prior in Bayes' rule::
-posterior: [...]
-likelihood: [...]
-prior: [...]
A: \(P(A \mid B)\); \(P(B \mid A)\); \(P(A)\)
title: robotics

Front: * Robotics — COMP3631
** Bayes' Rule
*** Why Bayes' rule is useful in robotics
Back: allows combining a prior belief about robot location with sensor likelihood to compute an updated posterior belief

Front: * Robotics — COMP3631
** Localisation
*** Why odometry alone is insufficient
Back: effector noise accumulates over time, making position error unbounded

Q: * Robotics — COMP3631
** Localisation
*** Three main sources of localisation uncertainty::
-[...]
-[...]
-[...]
A: effector (motion) noise; sensor noise; sensor aliasing
title: robotics

Front: * Robotics — COMP3631
** Localisation
*** Sensor aliasing definition
Back: different robot poses produce the same sensor reading, making disambiguation from a single measurement impossible

Front: * Robotics — COMP3631
** Localisation
*** Localisation goal
Back: maintain a probability distribution (belief) over all possible poses; reduce uncertainty by integrating motion and sensor data

Front: * Robotics — COMP3631
** Localisation
*** Probabilistic Basics
**** Belief \(bel(x_t)\) definition
Back: probability distribution over all possible robot poses at time \(t\)

Front: * Robotics — COMP3631
** Localisation
*** Probabilistic Basics
**** Uniform belief interpretation
Back: robot has no information about its location

Front: * Robotics — COMP3631
** Localisation
*** Probabilistic Basics
**** Gaussian belief \(\mathcal{N}(\mu,\sigma)\) interpretation
Back: robot is most likely near \(\mu\); \(\sigma\) reflects uncertainty

Front: * Robotics — COMP3631
** Localisation
*** Probabilistic Basics
**** Action update — effect on uncertainty
Back: increases uncertainty (motion is noisy)

Front: * Robotics — COMP3631
** Localisation
*** Probabilistic Basics
**** Perception update — effect on uncertainty
Back: decreases uncertainty (sensor observation narrows down location)

Front: * Robotics — COMP3631
** Localisation
*** Probabilistic Basics
**** Action update formula
Back: \[\overline{bel}(x_t) = \int p(x_t \mid u_t,\, x_{t-1}) \cdot bel(x_{t-1})\; dx_{t-1}\]

Front: * Robotics — COMP3631
** Localisation
*** Probabilistic Basics
**** Perception update formula
Back: \[bel(x_t) = \eta \cdot p(z_t \mid x_t) \cdot \overline{bel}(x_t)\] where \(\eta\) normalises so probabilities sum to 1

Front: * Robotics — COMP3631
** Localisation
*** Markov Localisation
**** Markov localisation representation
Back: discretise C-space into a grid; each cell stores the probability the robot is there

Front: * Robotics — COMP3631
** Localisation
*** Markov Localisation
**** Markov action update per cell \(c\)
Back: \[bel(c) = \sum_{c'} p(c \mid u_t,\, c') \cdot bel_{t-1}(c')\]

Front: * Robotics — COMP3631
** Localisation
*** Markov Localisation
**** \(p(c \mid u_t, c')\) comes from
Back: the effector noise model — probability of ending in \(c\) given command \(u_t\) from \(c'\)

Front: * Robotics — COMP3631
** Localisation
*** Markov Localisation
**** Markov perception update per cell \(c\)
Back: \[bel(c) = p(z_t \mid c) \cdot bel(c), \text{ then normalise over all cells}\]

Front: * Robotics — COMP3631
** Localisation
*** Markov Localisation
**** \(p(z_t \mid c)\) comes from
Back: the sensor noise model — probability of reading \(z_t\) if robot is at cell \(c\)

Front: * Robotics — COMP3631
** Localisation
*** Markov Localisation
**** Normalisation step purpose
Back: ensures all cell probabilities sum to 1 after the perception update

Front: * Robotics — COMP3631
** Localisation
*** Markov Localisation
**** Markov localisation drawback
Back: fine grid in 2D+orientation (e.g. 30m × 30m at 0.1m, 1° resolution) requires \(\approx 32\) million cell updates per step

Front: * Robotics — COMP3631
** Localisation
*** Particle Filtering (Monte Carlo Localisation)
**** Particle filter belief representation
Back: a set of \(M\) particles; each particle is a sampled pose hypothesis

Front: * Robotics — COMP3631
** Localisation
*** Particle Filtering (Monte Carlo Localisation)
**** Particle filter action update
Back: propagate each particle through the motion model — sample \(x_t^i \sim p(x_t \mid u_t,\, x_{t-1}^i)\)

Front: * Robotics — COMP3631
** Localisation
*** Particle Filtering (Monte Carlo Localisation)
**** Particle filter perception update — weight
Back: \[w^i = p(z_t \mid x_t^i)\] likelihood of observation given particle's pose

Front: * Robotics — COMP3631
** Localisation
*** Particle Filtering (Monte Carlo Localisation)
**** Particle filter resampling
Back: draw \(M\) new particles from current set with replacement, probability \(\propto w^i\)

Front: * Robotics — COMP3631
** Localisation
*** Particle Filtering (Monte Carlo Localisation)
**** Particle filter cycle
Back: Particles {x¹,…,xᴹ}  (current belief)
          ↓
  ACTION UPDATE
  Sample xᵢₜ ~ p(xₜ | uₜ, xᵢₜ₋₁)   [motion model]
          ↓
  PERCEPTION UPDATE
  Assign wⁱ = p(zₜ | xᵢₜ)   [sensor model]
          ↓
  RESAMPLE
  Draw M new particles with probability ∝ wⁱ
          ↓
  Updated particles  (refined belief)

Front: * Robotics — COMP3631
** Localisation
*** Particle Filtering (Monte Carlo Localisation)
**** Why can a particle be sampled multiple times?
Back: high-weight particles (better hypothesis matches) are more likely to be selected

Front: * Robotics — COMP3631
** Localisation
*** Particle Filtering (Monte Carlo Localisation)
**** Why is particle filter faster than Markov localisation?
Back: updates \(M\) particles (typically hundreds) vs millions of grid cells

Front: * Robotics — COMP3631
** Localisation
*** Particle Filtering (Monte Carlo Localisation)
**** Effect of too few particles (small \(M\))
Back: insufficient particles to represent the belief accurately; poor localisation

Front: * Robotics — COMP3631
** Localisation
*** Particle Filtering (Monte Carlo Localisation)
**** Effect of too many particles (large \(M\))
Back: accurate representation but slow update per time step

Front: * Robotics — COMP3631
** Localisation
*** Particle Filtering (Monte Carlo Localisation)
**** Markov vs particle filter comparison
Back: | Markov Localisation | Particle Filter (MCL)
Belief representation | Probability per grid cell | Set of \(M\) weighted pose samples
Scalability | Poor — millions of cells in 2D+θ | Good — updates M particles (typically 100s)
Accuracy | Limited by grid resolution | Concentrates particles where probability is high
Non-Gaussian beliefs | Handles naturally | Handles naturally
Computation per step | \(\mathcal{O}(\text{grid cells})\) | \(\mathcal{O}(M)\)

Front: * Robotics — COMP3631
** Imitation Learning
*** What does imitation learning enable?
Back: a robot to acquire motor skills from human demonstrations without hand-coding them

Front: * Robotics — COMP3631
** Imitation Learning
*** Probabilistic imitation learning key insight
Back: variance across demonstrations reveals which parts of the trajectory matter most — low variance = high precision required