Robotics foundations
The classic papers the field is built on, from kinematics, control and estimation to planning and grasp analysis.
Start here: seminal papers
A New Approach to Linear Filtering and Prediction Problems★ Must read
Journal of Basic Engineering, March 1960
Recast the Wiener filtering and prediction problem in state-space form, so the optimal estimate comes from a recursive linear filter whose gain is computed step by step from the estimation-error covariance. One derivation covers stationary and nonstationary statistics and growing or infinite memory, and filtering turns out to be the dual of the noise-free optimal regulator problem.
A Formal Basis for the Heuristic Determination of Minimum Cost Paths★ Must read
IEEE Transactions on Systems Science and Cybernetics, July 1968
The paper defines A*, a graph search that always expands the open node with the smallest f̂ = ĝ + ĥ, and proves it always finds a minimum-cost path when ĥ never overestimates the remaining cost. Under a consistency assumption on ĥ, no admissible algorithm that uses no more information expands fewer nodes.
Analysis of the Computed Torque Drive Method and Comparison with Conventional Position Servo for a Computer-Controlled ManipulatorSeminal
JPL Technical Memorandum 33-601, March 1973
A linear, single-joint analysis of the Stanford arm's computed-torque control (model-based feedforward torque plus inertia-scaled position, rate and integral feedback) against a conventional analog position servo. Computed torque follows the plan with zero error if the model is exact, while the conventional servo, even at a 100 rad/s natural frequency, lags about 1.15 degrees on a 5-second ±50-degree move.
Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography★ Must read
Communications of the ACM, June 1981
RANSAC fits a model to random minimal subsets of the data and keeps the hypothesis that the most other points agree with, instead of fitting all the data and pruning the worst residuals. Applied to locating a camera from landmarks with a new closed-form three-point solver, it kept every gross error out of the final fit in 50 synthetic problems.
Hybrid Position/Force Control of ManipulatorsSeminal
Journal of Dynamic Systems, Measurement, and Control, June 1981
A controller architecture that splits a task frame's directions into force-controlled and position-controlled ones with a binary selection matrix, while every joint contributes to both. On two axes of a Scheinman arm it tracks 1-10 Nt force steps with about 0.15 s rise time and under 1 Nt steady-state error.
An Iterative Image Registration Technique with an Application to Stereo VisionSeminal
International Joint Conference on Artificial Intelligence (IJCAI), August 1981
Align two images by using the spatial intensity gradient to step the displacement toward the best match in a Newton-Raphson-style iteration, instead of trying every displacement. A converging iteration takes O(M² log N) steps on average versus O(M²N²) for exhaustive search, and the same method recovers object depths in a stereo pair.
Articulated Hands: Force Control and Kinematic IssuesSeminal
The International Journal of Robotics Research, March 1982
Kinematic and control design of the three-finger, 9-DOF Stanford-JPL hand. A mobility analysis picks the finger layout (39 of 600 candidate designs pass), isotropic points mark where fingertip forces are most accurate, and a Cartesian hand controller sets object stiffness and internal grasp forces without inverse kinematics.
Measure of Manipulability for Robot ManipulatorsSeminal
Journal of the Robotics Society of Japan, February 1984
Study the manipulability measure w = √det(J Jᵀ), proportional to the volume of the end-effector velocity ellipsoid, and use it to find the best working posture of common arm types and a robot finger. A two-link arm is best with its elbow at 90° for any link lengths, and equal links are best for a fixed total length.
Impedance Control: An Approach to Manipulation, Part I: Theory★ Must read
Journal of Dynamic Systems, Measurement, and Control, March 1985
Hogan argues that a manipulator in contact cannot be controlled by commanding position or force alone; it must also be given an impedance, the force it produces in response to motion the environment imposes. Using bond graphs, he shows that a broad class of nonlinear manipulators splits into a virtual trajectory plus an impedance, and that impedances acting on the environment add even when they are nonlinear.
Obstacle Avoidance for Kinematically Redundant Manipulators in Dynamically Varying EnvironmentsSeminal
The International Journal of Robotics Research, September 1985
Keep a redundant arm's end-effector exactly on its commanded trajectory and use the Jacobian's null space to push the link point closest to an obstacle away from it. In simulation a 9-DoF arm spray-painting through a car-door window runs at a 102 ms control cycle.
A Robust Layered Control System for a Mobile RobotSeminal
IEEE Journal on Robotics and Automation, March 1986
Brooks splits mobile-robot control into stacked layers of behaviors (avoid, wander, explore) instead of a perceive-model-plan-act chain, and higher layers take over by suppressing the wires of lower ones. A real robot running the system went a number of hours in a lab and a machine room without hitting a moving or fixed obstacle.
Real-Time Obstacle Avoidance for Manipulators and Mobile RobotsSeminal
The International Journal of Robotics Research, March 1986
Khatib moves collision avoidance out of the path planner and into the low-level controller. The goal attracts the end effector and obstacles repel points on the arm through artificial potential fields, applied as operational-space forces. On a PUMA 560 the servo ran at 225 Hz and avoided moving obstacles seen by a vision system in real time.
A Computational Approach to Edge DetectionSeminal
IEEE Transactions on Pattern Analysis and Machine Intelligence, November 1986
Canny writes three goals for an edge detector (good detection, good localization, one response per edge) as functionals of the filter and optimizes them. The optimal step-edge operator is closely approximated by the first derivative of a Gaussian, about 20% below the optimum, and the full detector marks gradient maxima of the smoothed image and links them with hysteresis thresholds.
A Unified Approach for Motion and Force Control of Robot Manipulators: The Operational Space Formulation★ Must read
IEEE Journal on Robotics and Automation, February 1987
Khatib writes a manipulator's dynamics directly at its end-effector and uses them in one controller for both motion and contact force, extended to redundant arms and kinematic singularities. On a PUMA 560 it ran with a 200 Hz servo loop, and square-wave force commands gave rise times under 0.02 s.
Adaptive Control of Mechanical ManipulatorsSeminal
The International Journal of Robotics Research, June 1987
An adaptive computed-torque controller that estimates unknown mass and friction parameters on-line, with a Lyapunov proof that all signals stay bounded and tracking errors go to zero. On a simulated two-link arm, link masses (3 kg guessed, 4 kg true) and Coulomb friction (0 guessed, 2 Nm true) converge within several seconds.
A Combined Corner and Edge DetectorSeminal
Proceedings of the Alvey Vision Conference, September 1988
Moravec's corner detector, rebuilt on the local auto-correlation matrix of image gradients, so that one response R = Det(M) - k Tr(M)^2 labels each pixel as corner, edge or flat. The paper has no numbers; on outdoor image pairs it finds corners and thin edges and links them into an edge-vertex graph.
Numerical Filtering for the Operation of Robotic Manipulators through Kinematically Singular ConfigurationsSeminal
Journal of Robotic Systems, December 1988
Damped least-squares inverse kinematics with a cheap running estimate of the smallest singular value, plus extra damping applied only along the near-singular direction, lets a simulated arm pass through singularities with bounded joint velocity. At a planar arm's internal singularity, peak tracking error falls from 22% to under 4% of the commanded velocity compared with uniformly damped least squares.
Passive Dynamic WalkingSeminal
The International Journal of Robotics Research, April 1990
Two stiff legs with curved feet, pin-jointed at the hip, settle into a steady human-like gait down a shallow slope with no active control or energy input besides gravity. A step-to-step analysis predicts the gait and its stability, and a 50 cm test biped walks at 0.46 m/s on a 2.5% slope.
Planning Optimal GraspsSeminal
IEEE International Conference on Robotics and Automation (ICRA), May 1992
Two grasp quality measures, one bounding the largest finger force and one bounding the total finger force, each equal to the radius of the largest origin-centred ball inside a convex hull of contact wrenches. They lead to a grasp planner for polygons held by two- and three-jaw grippers that runs in O(n) for n edges in the two-jaw case.
Good Features to TrackSeminal
IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 1994
Pick feature windows whose 2x2 gradient matrix has a large smallest eigenvalue, because that is exactly when the tracker can solve for motion reliably, and drop features whose appearance, after an affine warp back to the first frame, stops matching. On a 26-frame real sequence with 102 features, this affine check singles out the occluded and depth-straddling features that a translation-only check misses.
Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces★ Must read
IEEE Transactions on Robotics and Automation, August 1996
The paper builds a roadmap once, from random collision-free configurations joined by a fast local planner, and answers each start-goal query by connecting both ends to it and searching the graph. For 7-dof planar robots among narrow passages, 60 s (fixed base) or 70 s (free base) of learning connects all eight hard test configurations in all 30 roadmaps, and a query then takes a fraction of a second.
A New Extension of the Kalman Filter to Nonlinear SystemsSeminal
Proc. SPIE 3068, Signal Processing, Sensor Fusion, and Target Recognition VI, July 1997
The unscented filter passes 2n+1 deterministically chosen sigma points through the nonlinear models instead of linearising them, which gives a mean accurate to second order without any Jacobians. In a simulated radar reentry-tracking problem it predicts its own error accurately, while the EKF's position covariance is over a hundred times smaller than its actual peak error.
Rapidly-Exploring Random Trees: A New Tool for Path Planning★ Must read
Technical Report TR 98-11, Iowa State University, October 1998
A search tree that grows by sampling a random state and steering the nearest vertex a small step toward it, so two states never have to be joined exactly and nonholonomic and kinodynamic systems can be planned for directly. In 2D convex spaces its paths are on average 1.3 to 2.0 times the optimal length, and the report applies it to problems of up to twelve degrees of freedom.
Monte Carlo Localization for Mobile RobotsSeminal
IEEE International Conference on Robotics and Automation (ICRA), May 1999
Monte Carlo Localization represents a mobile robot's position belief as a set of random samples and updates it with a particle filter, so the robot can localize itself without knowing where it started. With 5000 samples it tracked a museum tour-guide robot for 75 minutes and over 2200 m without once losing track.
Templates and Anchors: Neuromechanical Hypotheses of Legged Locomotion on LandSeminal
Journal of Experimental Biology, December 1999
A perspective that splits locomotion models into templates, the simplest models that capture a behavior (such as the spring-loaded inverted pendulum for running), and anchors, detailed models of legs, joints and muscles whose control collapses them onto a template. It offers twelve hypotheses, not new experiments.
Robotic Grasping and Contact: A ReviewSeminal
IEEE International Conference on Robotics and Automation (ICRA), April 2000
A short survey of two decades of analytical grasping theory, covering contact models, form and force closure, grasp force distribution, stability, grasp quality measures and the dynamics of frictional contact. It names accurate, tractable models of contact compliance and friction as the key open problems.
Robot Dynamics: Equations and AlgorithmsSeminal
IEEE International Conference on Robotics and Automation (ICRA), April 2000
A review of rigid-body robot dynamics that writes inverse dynamics (RNEA), the joint-space inertia matrix (CRBA) and forward dynamics (ABA) for tree-structured robots in one spatial-vector notation, then extends them to closed kinematic loops. It traces the move from O(N^4) Lagrangian methods to O(N) recursive algorithms; the ABA needs fewer operations than the CRBA once N > 9.
RRT-Connect: An Efficient Approach to Single-Query Path PlanningSeminal
IEEE International Conference on Robotics and Automation (ICRA), April 2000
RRT-Connect grows two Rapidly-exploring Random Trees, one from the start and one from the goal, and greedily extends each toward the other's newest vertex until they meet. It is probabilistically complete, needs no preprocessing, and solves 2D problems in 0.13-1.52 s and a 3D piano-moving problem in 12.5 s on a 270 MHz workstation.
A Flexible New Technique for Camera Calibration★ Must read
IEEE Transactions on Pattern Analysis and Machine Intelligence, November 2000
Calibrate a camera from a few photos of a printed flat pattern held at different orientations, using a closed-form solution from plane homographies and then a maximum-likelihood refinement with radial distortion. On a real camera, results from 2 to 5 images agree within about 2 pixels in focal length, with reprojection errors of 0.3-0.4 pixels.
Rapid Object Detection using a Boosted Cascade of Simple FeaturesSeminal
IEEE Conference on Computer Vision and Pattern Recognition (CVPR), December 2001
A face detector that scans a cascade of AdaBoost classifiers built on simple rectangle features, computed fast with an integral image, so most image windows are rejected after a few features. It matches the best published detection rates on MIT+CMU and runs at 15 frames per second on a 700 MHz Pentium III, about 15x faster than Rowley et al.
FastSLAM: A Factored Solution to the Simultaneous Localization and Mapping ProblemSeminal
AAAI Conference on Artificial Intelligence, July 2002
FastSLAM splits SLAM into a particle filter over robot paths and, inside each particle, a small Kalman filter for each landmark. A shared tree structure brings each update down to O(M log K) time, and the method mapped 50,000 simulated landmarks with 100 particles.
Hybrid Zero Dynamics of Planar Biped WalkersSeminal
IEEE Transactions on Automatic Control, January 2003
A feedback design for underactuated planar bipeds that keeps a two-dimensional zero-dynamics surface invariant through foot impacts, so walking stability reduces to a scalar linear return map. On a 5-link biped model, optimized controller parameters give exponentially stable walking at 1.05 m/s with a peak torque of about 47 Nm.
Biped Walking Pattern Generation by using Preview Control of Zero-Moment PointSeminal
IEEE International Conference on Robotics and Automation (ICRA), September 2003
The authors model a humanoid as a cart on a table and generate its center-of-mass trajectory with a preview controller that tracks the upcoming ZMP reference. A second preview pass corrects the simple model's error on the full HRP-2P multibody model, cutting the maximum ZMP error from 2.3 to 1.2 cm (x) and from 1.6 to 0.4 cm (y), and a simulated HRP-2P walks on spiral stairs.
Zero-Moment Point: Thirty Five Years of its LifeSeminal
International Journal of Humanoid Robotics, March 2004
The originators of the Zero-Moment Point restate it as the point on the sole where the ground reaction has no horizontal moment, and give a two-step test that computes it and checks it against the support polygon. They separate the real ZMP from the center of pressure and from a "fictitious" ZMP outside the foot, which signals that the robot is tipping over.
Distinctive Image Features from Scale-Invariant Keypoints★ Must read
International Journal of Computer Vision, November 2004
SIFT detects keypoints at extrema of a difference-of-Gaussian scale space and describes each with a 128-element histogram of local gradient orientations, invariant to scale and rotation. With a nearest-neighbor ratio test, Hough clustering and an affine fit, it recognizes occluded objects in clutter from as few as 3 matches in under 0.3 s.
GraspIt! A Versatile Simulator for Robotic GraspingSeminal
IEEE Robotics & Automation Magazine, December 2004
GraspIt! is a public simulator that imports hand, arm and object models, finds the contacts as a hand closes on an object, and scores the grasp on the fly with wrench-space quality measures. It ships with five hand models, a Puma arm and a mobile base, and a rigid-body dynamics engine for simulating how grasps form.
Efficient Bipedal Robots Based on Passive-Dynamic WalkersSeminal
Science, February 2005
Three bipeds built at Cornell, Delft and MIT add small ankle or hip actuators to passive-dynamic ramp walkers, so they walk on level ground with very simple control. The Cornell biped's mechanical cost of transport is about 0.055, close to a human's 0.05; the authors estimate 1.6 for Honda's Asimo.
Histograms of Oriented Gradients for Human DetectionSeminal
IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2005
Dense grids of locally contrast-normalized histograms of gradient orientations (HOG), fed to a linear SVM, detect pedestrians far better than wavelet, PCA-SIFT or shape-context features. They give near-perfect separation on the MIT set and at least an order of magnitude fewer false positives on the new, harder INRIA dataset.
The GraphSLAM Algorithm with Applications to Large-Scale Mapping of Urban StructuresSeminal
The International Journal of Robotics Research, May 2006
GraphSLAM turns every odometry reading and measurement into a soft constraint in a sparse graph, eliminates the map features to leave a smaller problem over robot poses, and solves it. It builds maps with 10^8 or more features; relaxing the largest urban data set (600 m by 800 m, a dozen loops) takes about 30 seconds.
Compliant Leg Behaviour Explains Basic Dynamics of Walking and RunningSeminal
Proceedings of the Royal Society B, November 2006
Add a second spring leg to the spring-mass running model and it walks, reproducing the M-shaped vertical ground reaction force, small body bob and out-of-phase energy changes of human walking at about 1.2 m/s, which the stiff-legged inverted pendulum cannot. The same model also runs, above a speed gap of about 1.5 m/s.
Visual Servo Control, Part I: Basic ApproachesSeminal
IEEE Robotics & Automation Magazine, December 2006
A tutorial that casts visual servoing as driving a visual-feature error to zero with the velocity law v = -lambda L+ e, then compares image-based (IBVS) and position-based (PBVS) control. It reports no benchmark numbers; noise-free simulations of one positioning task show IBVS is only locally stable, while PBVS is globally stable only if the pose estimate is perfect.
Capture Point: A Step toward Humanoid Push RecoverySeminal
IEEE-RAS International Conference on Humanoid Robots (Humanoids), December 2006
Defines the Capture Point, the spot on the ground where a pushed biped must step to come to a complete stop, and computes it in closed form for a linear inverted pendulum with a flywheel body. In simulation, a planar biped walking at 0.5 m/s stops in a single step by lunging its body.
Robotic Grasping of Novel Objects using VisionSeminal
The International Journal of Robotics Research, February 2008
A classifier trained only on synthetic images of five object classes predicts where in an image to grasp an object, and the predictions from two or more views are triangulated into a 3-d grasp point without building a 3-d model. A 5-DoF arm picked up novel objects 87.8% of the time and unloaded a dishwasher with 80% success.
iSAM: Incremental Smoothing and MappingSeminal
IEEE Transactions on Robotics, December 2008
iSAM solves SLAM as sparse least squares and updates the QR factor of the smoothing problem with Givens rotations as measurements arrive, reordering variables periodically to keep it sparse. On the 26-minute Victoria Park run it computes the full, exact solution with data association after every frame in 7.7 minutes, over 3x faster than real time.
CHOMP: Gradient Optimization Techniques for Efficient Motion PlanningSeminal
IEEE International Conference on Robotics and Automation (ICRA), May 2009
CHOMP plans by optimizing the trajectory directly, using a covariant gradient step that keeps it smooth while pushing it out of obstacles, starting from a straight line that may pass through obstacles. Without a separate planner it found collision-free paths for 99 of 105 household problems on a WAM arm, and it is the footstep controller for the LittleDog quadruped.
g2o: A General Framework for Graph OptimizationSeminal
IEEE International Conference on Robotics and Automation (ICRA), May 2011
An open-source C++ framework that optimizes any least-squares problem that can be written as a graph, such as 2D/3D SLAM and bundle adjustment, once the user defines an error function and an update operator. On ten datasets it is faster per iteration than √SAM on every SLAM dataset, on par with problem-specific solvers elsewhere, and about twice as fast as RobotVision.
ORB: An Efficient Alternative to SIFT or SURFSeminal
IEEE International Conference on Computer Vision (ICCV), November 2011
ORB is a binary feature that adds an orientation to FAST corners and learns a rotation-aware set of BRIEF tests. It matches about as well as SIFT in their tests and takes 15.3 ms per 640x480 frame, against 217.3 ms for SURF and 5228.7 ms for SIFT.
ImageNet Classification with Deep Convolutional Neural NetworksSeminal
Advances in Neural Information Processing Systems (NeurIPS), December 2012
An eight-layer convolutional network with 60 million parameters, trained on two GPUs with ReLUs, data augmentation and dropout, classifies the 1000 ImageNet classes at 17.0% top-5 test error on ILSVRC-2010, against 25.7% for the best earlier result. An ensemble of these networks won ILSVRC-2012 with 15.3% versus 26.2% for the runner-up.
Occupancy Grids: A Stochastic Spatial Representation for Active Robot PerceptionSeminal
March 2013
Represent the robot's surroundings as a grid of cells, each holding a Bayesian estimate of the probability that it is occupied, updated from noisy range readings taken from many views and sensors. The paper reviews the framework and shows sonar and sonar-plus-stereo maps, path planning and pose-uncertainty handling done directly on the grid, without quantitative metrics.
Estimating Uncertain Spatial Relationships in RoboticsSeminal
March 2013
Stack the poses of the robot and every mapped object into one state vector with a full covariance matrix (the stochastic map), and build and update it with pose compounding, inversion and an extended Kalman filter. The paper cites Monte Carlo tests in which these linearized estimates stayed within 1% of the true means and variances for angular errors up to 5 degrees.
Finding Locally Optimal, Collision-Free Trajectories with Sequential Convex OptimizationSeminal
Robotics: Science and Systems (RSS), June 2013
Trajopt plans robot motion by sequential convex optimization, penalizing collisions through signed distances to the volume a link sweeps between waypoints, so paths are safe in continuous time. With four initializations it solved 99% of 198 PR2 arm problems in 0.32 s on average, against 97% in 1.2 s for OMPL's RRTConnect and 85% in 6.0 s for CHOMP.
Summaries are written automatically from each paper's text. Figures and videos come from the paper and its project page; all credit goes to the authors.