Algorithmic Foundations of Robotics XI

Algorithmic Foundations of Robotics XI: Selected Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics

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.

Table of Contents

Chapter 1. Efficient Multi-robot Motion Planning for Unlabeled Discs in Simple Polygons
Chapter 2. Navigation of Distinct Euclidean Particles via Hierarchical Clustering
Chapter 3. Coalition Formation Games for Dynamic Multirobot Tasks
Chapter 4. Active Control Strategies for Discovering and Localizing Devices with Range-Only Sensors
Chapter 5. Aggressive Moving Obstacle Avoidance Using a Stochastic Reachable Set Based Potential Field
Chapter 6. Distributed Range-Based Relative Localization of Robot Swarms
Chapter 7. Computing Large Convex Regions of Obstacle-Free Space Through Semidefinite Programming
Chapter 8. A Region-Based Strategy for Collaborative Roadmap Construction
Chapter 9. Efficient Sampling-Based Approaches to Optimal Path Planning in Complex Cost Spaces
Chapter 10. Real-Time Predictive Modeling and Robust Avoidance of Pedestrians with Uncertain, Changing Intentions
Chapter 11. FFRob: An Efficient Heuristic for Task and Motion Planning
Chapter 12. Fast Nearest Neighbor Search in SE(3) for Sampling-Based Motion Planning
Chapter 13. Trackability with Imprecise Localization
Chapter 14. Kinodynamic RRTs with Fixed Time Step and Best-Input Extension Are Not Probabilistically Complete
Chapter 15. Featureless Motion Vector-Based Simultaneous Localization, Planar Surface Extraction, and Moving Obstacle Tracking
Chapter 16. Sparse Methods for Efficient Asymptotically Optimal Kinodynamic Planning
Chapter 17. Adaptive Informative Path Planning in Metric Spaces
Chapter 18. The Feasible Transition Graph: Encoding Topology and Manipulation Constraints for Multirobot Push-Planning
Chapter 19. Collision Prediction Among Rigid and Articulated Obstacles with Unknown Motion
Chapter 20. Asymptotically Optimal Stochastic Motion Planning with Temporal Goals
Chapter 21. Resolution-Exact Algorithms for Link Robots
Chapter 22. Optimal Trajectories for Planar Rigid Bodies with Switching Costs
Chapter 23. Maximum-Reward Motion in a Stochastic Environment: The Nonequilibrium Statistical Mechanics Perspective
Chapter 24. Optimal Path Planning in Cooperative Heterogeneous Multi-robot Delivery Systems
Chapter 25. Composing Dynamical Systems to Realize Dynamic Robotic Dancing
Chapter 26. The Lion and Man Game on Convex Terrains
Chapter 27. RRTX: Real-Time Motion Planning/ Replanning for Environments with Unpredictable Obstacles
Chapter 28. Orienting Parts with Shape Variation
Chapter 29. Smooth and Dynamically Stable Navigation of Multiple Human-Like Robots
Chapter 30. Scaling up Gaussian Belief Space Planning Through Covariance-Free Trajectory Optimization and Automatic Differentiation
Chapter 31. Planning Curvature and Torsion Constrained Ribbons in 3D with Application to Intracavitary Brachytherapy
Chapter 32. A Quadratic Programming Approach to Quasi-Static Whole-Body Manipulation
Chapter 33. On-line Coverage of Planar Environments by a Battery Powered Autonomous Mobile Robot
Chapter 34. Finding a Needle in an Exponential Haystack: Discrete RRT for Exploration of Implicit Roadmaps in Multi-robot Motion Planning
Chapter 35. Stochastic Extended LQR: Optimization-Based Motion Planning Under Uncertainty
Chapter 36. An Approximation Algorithm for Time Optimal Multi-Robot Routing
Chapter 37. Decidability of Robot Manipulation Planning: Three Disks in the Plane
Chapter 38. A Topological Perspective on Cycling Robots for Full Tree Coverage
Chapter 39. Towards Arranging and Tightening Knots and Unknots with Fixtures
Chapter 40. Asymptotically Optimal Feedback Planning: FMM Meets Adaptive Mesh Refinement
Chapter 41. Online Task Planning and Control for Aerial Robots with Fuel Constraints in Winds
Chapter 42. Pebble Motion on Graphs with Rotations: Efficient Feasibility Tests and Planning Algorithms