Algorithms are a fundamental component of robotic systems. Robot algorithms process inputs from sensors that provide noisy and partial data, build geometric and physical models of the world, plan high-and low-level actions at different time horizons, and execute these actions on actuators with limited precision. The design and analysis of robot algorithms raise a unique combination of questions from many elds, including control theory, computational geometry and topology, geometrical and physical modeling, reasoning under uncertainty, probabilistic algorithms, game theory, and theoretical computer science.

The Workshop on Algorithmic Foundations of Robotics (WAFR) is a single-track meeting of leading researchers in the eld of robot algorithms. Since its inception in 1994, WAFR has been held every other year, and has provided one of the premiere venues for the publication of some of the eld's most important and lasting contributions.

This books contains the proceedings of the tenth WAFR, held on June 13{15 2012 at the Massachusetts Institute of Technology. The 37 papers included in this book cover a broad range of topics, from fundamental theoretical issues in robot motion planning, control, and perception, to novel applications.

Inhalt

The Minimum Constraint Removal Problem with Three Robotics Applications.- Hierarchical Decision Theoretic Planning for Navigation Among Movable Obstacles.- Robust complete path planning in the plane.- "Con_gurations and Path Planning of Convex Planar Polygonal Loops".- Equilibrium Con_gurations of a Kirchho_ Elastic Rod Under Quasi-Static Manipulation.- From Discrete to Continuous Motion Planning.- Ray-Shooting Algorithms for Robotics.- Optimal Gap Navigation for a Disc Robot.- Min-Max Latency Walks: Approximation Algorithms for Monitoring Vertex-Weighted Graphs.- Multi-agent Path Planning and Network Flow.- Trajectory Planning and Assignment in Multirobot Sys- tems.- k-Color Multi-Robot Motion Planning.- Distributed Construction of Truss Structures.- Space-time Group Motion Planning.- Multi-Robot Coverage and Exploration in Non-Euclidean Metric Spaces.- Lion and Man with Visibility in Monotone Polygons.- Sparse Roadmap Spanners.- Toggle PRM: A Coordinated Mapping of C-free and C-.- On the Power of Manifold Samples in Exploring Con_g- uration Spaces and the Dimensionality of Narrow Passages.- Sampling extremal trajectories for planar rigid bodies.- Convex Hull Asymptotic Shape Evolution.- E_cient Collision Checking in Sampling-based Motion Planning.- Faster Sample-based Motion Planning using Instance- based Learning.- Scale-Free Coordinates for Multi-Robot Systems with Bearing-only Sensors.- Mapping polygons with agents that measure angles.- Counting Moving Bodies Using Sparse Sensor Beams.- Convex receding horizon control in non-Gaussian belief space.- Planar Uncertainty Propagation and a Probabilistic Al- gorithm for Interception.- Intention-Aware Motion Planning Tirthankar Bandyopadhyay, Kok Sung Won, Emilio Frazzoli, David.- Point-Based Policy Modi_er: Coping with Changes in POMDP Models.- From Formal Methods to Algorithmic Implementation of Human Inspired Control on Bipedal Robots.- Direct Trajectory Optimization of Rigid Body Dynamical Systems Through Contact.- Robust Online Motion Planning with Regions of Finite Time Invariance.- Towards Consistent Vision-aided Inertial Navigation.- Learning to Segment and Track in RGBD.- path inference _lter: model-based low-latency map matching of probe vehicle data.- Predicting Pedestrian Trajectories using Velocity-Space Reasoning.