Algorithmic Foundations of Robotics X: Proceedings of the Tenth Workshop on the Algorithmic Foundations of Robotics (Springer Tracts in Advanced Robotics (86))

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. Front Matter....Pages 1-14 The Minimum Constraint Removal Problem with Three Robotics Applications....Pages 1-17 Hierarchical Decision Theoretic Planning for Navigation Among Movable Obstacles....Pages 19-35 Robust Complete Path Planning in the Plane....Pages 37-52 Configurations and Path Planning of Convex Planar Polygonal Loops....Pages 53-69 Equilibrium Configurations of a Kirchhoff Elastic Rod under Quasi-static Manipulation....Pages 71-87 From Discrete to Continuous Motion Planning....Pages 89-104 Ray-Shooting Algorithms for Robotics....Pages 105-121 Optimal Gap Navigation for a Disc Robot....Pages 123-138 Min-Max Latency Walks: Approximation Algorithms for Monitoring Vertex-Weighted Graphs....Pages 139-155 Multi-agent Path Planning and Network Flow....Pages 157-173 Trajectory Planning and Assignment in Multirobot Systems....Pages 175-190 k -Color Multi-robot Motion Planning....Pages 191-207 Distributed Construction of Truss Structures....Pages 209-225 Space-Time Group Motion Planning....Pages 227-243 Multi-robot Coverage and Exploration in Non-Euclidean Metric Spaces....Pages 245-262 Lion and Man with Visibility in Monotone Polygons....Pages 263-278 Sparse Roadmap Spanners....Pages 279-296 Toggle PRM: A Coordinated Mapping of C-Free and C-Obstacle in Arbitrary Dimension....Pages 297-312 On the Power of Manifold Samples in Exploring Configuration Spaces and the Dimensionality of Narrow Passages....Pages 313-329 Sampling Extremal Trajectories for Planar Rigid Bodies....Pages 331-347 Convex Hull Asymptotic Shape Evolution....Pages 349-364 Efficient Collision Checking in Sampling-Based Motion Planning....Pages 365-380 Faster Sample-Based Motion Planning Using Instance-Based Learning....Pages 381-396 Scale-Free Coordinates for Multi-robot Systems with Bearing-Only Sensors....Pages 397-414 Mapping Polygons with Agents That Measure Angles....Pages 415-425 Counting Moving Bodies Using Sparse Sensor Beams....Pages 427-442 Convex Receding Horizon Control in Non-Gaussian Belief Space....Pages 443-458 Planar Uncertainty Propagation and a Probabilistic Algorithm for Interception....Pages 459-474 Intention-Aware Motion Planning....Pages 475-491 Point-Based Policy Transformation: Adapting Policy to Changing POMDP Models....Pages 493-509 From Formal Methods to Algorithmic Implementation of Human Inspired Control on Bipedal Robots....Pages 511-526 Direct Trajectory Optimization of Rigid Body Dynamical Systems through Contact....Pages 527-542 Robust Online Motion Planning with Regions of Finite Time Invariance....Pages 543-558 Towards Consistent Vision-Aided Inertial Navigation....Pages 559-574 Learning to Segment and Track in RGBD....Pages 575-590 The Path Inference Filter: Model-Based Low-Latency Map Matching of Probe Vehicle Data....Pages 591-607 Predicting Pedestrian Trajectories Using Velocity-Space Reasoning....Pages 609-623 Erratum: Direct Trajectory Optimization of Rigid Body Dynamical Systems through Contact....Pages E1-E1 Back Matter....Pages 1-2 This is the proceedings of the tenth WAFR, held at Massachusetts Institute of Technology in June 2012. Its 37 papers address a broad range of topics, from fundamental theoretical issues in robot motion planning, control and perception, to novel applications. From the Contents: 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.