Algorithmic Foundations of Robotics XI: Selected Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics (Springer Tracts in Advanced Robotics Book 107)

This carefully edited volume is the outcome of the eleventh edition of the Workshop on Algorithmic Foundations of Robotics (WAFR), which is the premier venue showcasing cutting edge research in algorithmic robotics. The eleventh WAFR, which was held August 3-5, 2014 at Boğaziçi University in Istanbul, Turkey continued this tradition. This volume contains extended versions of the 42 papers presented at WAFR. These contributions highlight the cutting edge research in classical robotics problems (e.g. manipulation, motion, path, multi-robot and kinodynamic planning), geometric and topological computation in robotics as well novel applications such as informative path planning, active sensing and surgical planning. This book - rich by topics and authoritative contributors - is a unique reference on the current developments and new directions in the field of algorithmic foundations. Front Matter....Pages i-xix Efficient Multi-robot Motion Planning for Unlabeled Discs in Simple Polygons....Pages 1-17 Navigation of Distinct Euclidean Particles via Hierarchical Clustering....Pages 19-36 Coalition Formation Games for Dynamic Multirobot Tasks....Pages 37-54 Active Control Strategies for Discovering and Localizing Devices with Range-Only Sensors....Pages 55-71 Aggressive Moving Obstacle Avoidance Using a Stochastic Reachable Set Based Potential Field....Pages 73-89 Distributed Range-Based Relative Localization of Robot Swarms....Pages 91-107 Computing Large Convex Regions of Obstacle-Free Space Through Semidefinite Programming....Pages 109-124 A Region-Based Strategy for Collaborative Roadmap Construction....Pages 125-141 Efficient Sampling-Based Approaches to Optimal Path Planning in Complex Cost Spaces....Pages 143-159 Real-Time Predictive Modeling and Robust Avoidance of Pedestrians with Uncertain, Changing Intentions....Pages 161-177 FFRob: An Efficient Heuristic for Task and Motion Planning....Pages 179-195 Fast Nearest Neighbor Search in SE(3) for Sampling-Based Motion Planning....Pages 197-214 Trackability with Imprecise Localization....Pages 215-231 Kinodynamic RRTs with Fixed Time Step and Best-Input Extension Are Not Probabilistically Complete....Pages 233-244 Featureless Motion Vector-Based Simultaneous Localization, Planar Surface Extraction, and Moving Obstacle Tracking....Pages 245-261 Sparse Methods for Efficient Asymptotically Optimal Kinodynamic Planning....Pages 263-282 Adaptive Informative Path Planning in Metric Spaces....Pages 283-300 The Feasible Transition Graph: Encoding Topology and Manipulation Constraints for Multirobot Push-Planning....Pages 301-318 Collision Prediction Among Rigid and Articulated Obstacles with Unknown Motion....Pages 319-333 Asymptotically Optimal Stochastic Motion Planning with Temporal Goals....Pages 335-352 Resolution-Exact Algorithms for Link Robots....Pages 353-370 Optimal Trajectories for Planar Rigid Bodies with Switching Costs....Pages 371-387 Maximum-Reward Motion in a Stochastic Environment: The Nonequilibrium Statistical Mechanics Perspective....Pages 389-406 Optimal Path Planning in Cooperative Heterogeneous Multi-robot Delivery Systems....Pages 407-423 Composing Dynamical Systems to Realize Dynamic Robotic Dancing....Pages 425-442 The Lion and Man Game on Convex Terrains....Pages 443-460 Orienting Parts with Shape Variation....Pages 461-478 Smooth and Dynamically Stable Navigation of Multiple Human-Like Robots....Pages 479-496 Scaling up Gaussian Belief Space Planning Through Covariance-Free Trajectory Optimization and Automatic Differentiation....Pages 497-513 Planning Curvature and Torsion Constrained Ribbons in 3D with Application to Intracavitary Brachytherapy....Pages 515-533 A Quadratic Programming Approach to Quasi-Static Whole-Body Manipulation....Pages 535-552 On-line Coverage of Planar Environments by a Battery Powered Autonomous Mobile Robot....Pages 553-570 Finding a Needle in an Exponential Haystack: Discrete RRT for Exploration of Implicit Roadmaps in Multi-robot Motion Planning....Pages 571-589 Stochastic Extended LQR: Optimization-Based Motion Planning Under Uncertainty....Pages 591-607 An Approximation Algorithm for Time Optimal Multi-Robot Routing....Pages 609-626 Decidability of Robot Manipulation Planning: Three Disks in the Plane....Pages 627-640 A Topological Perspective on Cycling Robots for Full Tree Coverage....Pages 641-657 Towards Arranging and Tightening Knots and Unknots with Fixtures....Pages 659-675 Asymptotically Optimal Feedback Planning: FMM Meets Adaptive Mesh Refinement....Pages 677-694 Online Task Planning and Control for Aerial Robots with Fuel Constraints in Winds....Pages 695-710 Pebble Motion on Graphs with Rotations: Efficient Feasibility Tests and Planning Algorithms....Pages 711-727 Back Matter....Pages 729-746 ....Pages 747-751 This carefully edited volume is the outcome of the eleventh edition of the Workshop on Algorithmic Foundations of Robotics (WAFR), which is the premier venue showcasing cutting edge research in algorithmic robotics. The eleventh WAFRm which was held August 3-5, 2014 at Boǧaziçi University in Istanbul, Turkey continued this tradition. This colume contains extended versions of the 42 papers presented at WAFR. These contributions highlight the cutting edge research in classical robotics problems (e.g. manipulation, motion, path, multi-robot and kinodynamic planning), geometric and topological computation in robotics ass well as applications such as informative path planning, active sensing and surgical planning. This book - rich by topics and authoritative contributors - ia a unique reference on the current developments and new directions in the field of algorithmic foundations -- Book cover