Algorithms are a fundamental component of robotic systems: they control or reason about motion and perception in the physical world. They receive input from noisy sensors, consider geometric and physical constraints, and operate on the world through imprecise actuators. The design and analysis of robot algorithms therefore raises a unique combination of questions in control theory, computational and differential geometry, and computer science.

This book contains the proceedings from the 2006 Workshop on the Algorithmic Foundations of Robotics. This biannual workshop is a highly selective meeting of leading researchers in the field of algorithmic issues related to robotics. The 32 papers in this book span a wide variety of topics: from fundamental motion planning algorithms to applications in medicine and biology, but they have in common a foundation in the algorithmic problems of robotic systems.

Inhalt

Probabilistic Roadmap Methods (PRMs).- Quantitative Analysis of Nearest-Neighbors Search in High-Dimensional Sampling-Based Motion Planning.- Path Deformation Roadmaps.- Workspace-Based Connectivity Oracle: An Adaptive Sampling Strategy for PRM Planning.- Incremental Map Generation (IMG).- Planning for Movable and Moving Obstacles.- Caging Polygons with Two and Three Fingers.- An Effective Framework for Path Planning Amidst Movable Obstacles.- Planning the Shortest Safe Path Amidst Unpredictably Moving Obstacles.- Planning Among Movable Obstacles with Artificial Constraints.- Navigation, SLAM, and Error Models for Filtering/Control.- Inferring and Enforcing Relative Constraints in SLAM.- Second-Order Theory of Error Propagation on Motion Groups.- Extensive Representations and Algorithms for Nonlinear Filtering and Estimation.- Geometric Computations and Applications.- An Experimental Study of Weighted k-Link Shortest Path Algorithms.- Low-Discrepancy Curves and Efficient Coverage of Space.- The Snowblower Problem.- Stratified Deformation Space and Path Planning for a Planar Closed Chain with Revolute Joints.- Motion Planning.- Competitive Disconnection Detection in On-Line Mobile Robot Navigation.- A Simple Path Non-existence Algorithm Using C-Obstacle Query.- RESAMPL: A Region-Sensitive Adaptive Motion Planner.- Motion Planning for a Six-Legged Lunar Robot.- Applications in Medicine and Biology.- Constant-Curvature Motion Planning Under Uncertainty with Applications in Image-Guided Medical Needle Steering.- Extended Abstract: Structure Determination of Symmetric Protein Complexes by a Complete Search of Symmetry Configuration Space Using NMR Distance Restraints.- Control and Planning for Mechanical Systems.- The Minimum-Time Trajectories for an Omni-Directional Vehicle.- Mechanical Manipulation Using Reduced Models of Uncertainty.- Motion Planning for Variable Inertia Mechanical Systems.- Sampling-Based Falsification and Verification of Controllers for Continuous Dynamic Systems.- Sensor Networks and Reconfiguration.- Surrounding Nodes in Coordinate-Free Networks.- Passive Mobile Robot Localization within a Fixed Beacon Field.- Efficient Motion Planning Strategies for Large-Scale Sensor Networks.- Asymptotically Optimal Kinodynamic Motion Planning for Self-reconfigurable Robots.- Planning for Games, VR, and Humanoid Motion.- Visibility-Based Pursuit-Evasion with Bounded Speed.- Planning Near-Optimal Corridors Amidst Obstacles.- Using Motion Primitives in Probabilistic Sample-Based Planning for Humanoid Robots.