Algorithmic Foundations of Robotics XII: Proceedings of the Twelfth Workshop on the Algorithmic Foundations of Robotics (Springer Proceedings in Advanced Robotics, 13)

This book presents the outcomes of the 12th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2016). WAFR is a prestigious, single-track, biennial international meeting devoted to recent advances in algorithmic problems in robotics. Robot algorithms are an important building block of robotic systems and are used to process inputs from users and sensors, perceive and build models of the environment, plan low-level motions and high-level tasks, control robotic actuators, and coordinate actions across multiple systems. However, developing and analyzing these algorithms raises complex challenges, both theoretical and practical. Advances in the algorithmic foundations of robotics have applications to manufacturing, medicine, distributed robotics, human–robot interaction, intelligent prosthetics, computer animation, computational biology, and many other areas. The 2016 edition of WAFR went back to its roots and was held in San Francisco, California – the city where the very first WAFR was held in 1994. Organized by Pieter Abbeel, Kostas Bekris, Ken Goldberg, and Lauren Miller, WAFR 2016 featured keynote talks by John Canny on “A Guided Tour of Computer Vision, Robotics, Algebra, and HCI,” Erik Demaine on “Replicators, Transformers, and Robot Swarms: Science Fiction through Geometric Algorithms,” Dan Halperin on “From Piano Movers to Piano Printers: Computing and Using Minkowski Sums,” and by Lydia Kavraki on “20 Years of Sampling Robot Motion.” Furthermore, it included an Open Problems Session organized by Ron Alterovitz, Florian Pokorny, and Jur van den Berg. There were 58 paper presentations during the three-day event. The organizers would like to thank the authors for their work and contributions, the reviewers for ensuring the high quality of the meeting, the WAFR Steering Committee led by Nancy Amato as well as WAFR’s fiscal sponsor, the International Federation of Robotics Research (IFRR), led by Oussama Khatib and Henrik Christensen. WAFR 2016 was an enjoyable and memorable event. Foreword Contents 1 Multiple Start Branch and Prune Filtering Algorithm for Nonconvex Optimization 1 Introduction 2 Background 3 Modeling 4 Results 5 Conclusion Acknowledgments References 2 Designing Sparse Reliable Pose-Graph SLAM: A Graph-Theoretic Approach 1 Introduction 2 Preliminaries 3 D-Optimality via Graph Synthesis 4 Synthesis of Near-t-Optimal Graphs 5 Conclusion Bibliography 3 Batch Misalignment Calibration of Multiple Three-Axis Sensors 1 Introduction 2 Theory 3 Simulation 4 Experimental Results 5 Conclusions References 4 High-Accuracy Preintegration for Visual-Inertial Navigation 1 Introduction 2 Related Work 3 Graph-based Batch Optimization 4 Analytical IMU Preintegration 5 Sliding-Window Visual Tracking 6 Experimental Results 7 Conclusions and Future Work References 5 A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group 1 Introduction 2 Problem formulation 3 Forming the semidefinite relaxation 4 The SE-Sync algorithm 5 Experimental results 6 Conclusion Bibliography 6 Autonomous Visual Rendering using Physical Motion 1 Introduction 2 Methods 3 Examples 4 Conclusion 5 Acknowledgements References 7 Cloud-based Motion Plan Computation for Power-Constrained Robots 1 Introduction 2 Related Work 3 Problem Definition 5 Results 6 Conclusion References 4 Method 8 Combining System Design and Path Planning 1 Introduction 2 Problem Formulation and Approach 3 Algorithm 4 Empirical Analysis and Results 5 Conclusion Acknowledgment References 9 Language-Guided Sampling-based Planning using Temporal Relaxation 1 Introduction 2 Preliminaries 3 Problem Formulation 4 Solution 5 Case Studies 6 Conclusion Acknowledgments. References 10 Generating Plans that Predict Themselves 1 Introduction 2 Defining and Optimizing for t-Predictability 3 Online Experiment 4 User Study 5 Discussion References 11 Sensor-Based Reactive Navigation in Unknown Convex Sphere Worlds 1 Introduction 2 Problem Formulation 3 Encoding Collisions via Separating Hyperplanes 4 Robot Navigation via Separating Hyperplanes 5 Numerical Simulations 6 Conclusions References 12 You can’t save all the pandas: impossibility results for privacy-preserving tracking 1 Introduction 2 Problem description: one-dimensional panda tracking 3 Privacy-preserving tracking 4 Beyond one-dimensional tracking 5 Related work 6 Conclusion and future work Acknowledgements References 13 Approximation Algorithms for Tours of Height-varying View Cones 1 Introduction 2 Problem Statement 3 Optimal Maximum Height Attained 4 Algorithm 5 Experiments 6 Conclusion References 14 Competitive Two Team Target Search Game with Communication Symmetry and Asymmetry 1 Introduction 2 Related Work 3 Preliminaries 4 Optimal Strategies for Ideal Games 5 Simulations and Experiments 6 Discussion 7 Summary and Conclusions Acknowledgments References 15 Beyond the planning potpourri: reasoning about label transformations on procrustean graphs 1 Introduction 2 Procrustean graphs 3 Plans and planning problems 4 Label maps and the damage they inflict 5 Related work and outlook 6 Conclusion References 16 Importance Sampling for Online Planning under Uncertainty 1 Introduction 2 Background 3 IS-DESPOT 4 Importance Distributions 5 Experiments 6 Conclusion References 17 Reactive Motion Planning in Uncertain Environments via Mutual Information Policies 1 Introduction 2 Background 3 Problem Definition 4 Properties and Complexity of Reactive Planning 5 Scalable Policy Generation 6 Simulation Results 7 Conclusion References 18 Linearization in Motion Planning under Uncertainty 1 Introduction 2 Related work 3 Problem modelling 4 Statistical-distance-based Non-linearity Measure (SNM) 5 SNM-Planner: An Application of SNM for Planning 6 Experimental Results 7 Summary and Future Work References 19 Motion Planning for Active Data Association and Localization in Non-Gaussian Belief Spaces 1 Introduction 2 Related Work 3 Preliminaries and Problem 4 Methodology 5 Experimental Results 6 Conclusion References 20 Integrated Perception and Control at High Speed: Evaluating Collision Avoidance Maneuvers Without Maps 1 Introduction 2 Related Work 3 Generalized Formulation for Collision Avoidance 4 Implementation for High Speed Quadrotor Flight 5 Simulation Experimental Setup 6 Simulation Results and Discussion 7 Future Work 8 Acknowledgements References 21 Risk-Aware Graph Search with Dynamic Edge Cost Discovery 1 Introduction 2 Related Work 3 Problem Formulation 4 Risk-Aware Graph Search (RAGS) 5 Comparison to Existing Search Algorithms 6 Satellite Data Experiments 7 Conclusion Acknowledgements References 22 Symbolic Computation of Dynamics on Smooth Manifolds 1 Introduction 2 Mathematical Background 3 Computational Design of Dynamics Solver 4 Results of Computing Symbolic Models 5 Discussion 6 Conclusion 7 Acknowledgements References 23 A Linear-Time Variational Integrator for Multibody Systems 1 Introduction 2 Background 3 Linear-Time Variational Integrator 4 Experimental Results 5 Conclusion Acknowledgments References 24 A General Algorithm for Time-Optimal Trajectory Generation Subject to Minimum and Maximum Constraints 1 Introduction 2 Related Work 3 Problem Definitions 4 Classical Phase Plane Navigation Overview 5 Traj Alg and AVI Alg, Algorithms for Phase Plane Navigation 6 Phase Plane Parameterizations 7 Results 8 Conclusion Acknowledgments References 25 Dynamic Walking on Stepping Stones with Gait Library and Control Barrier Functions 1 Introduction 2 Dynamical Model for Walking 3 Optimization and Gait library 4 Control Barrier Function based controller for steppingstones 5 Numerical Validation 6 Conclusion Acknowledgements References 26 Algorithmic Foundations of Realizing Multi-Contact Locomotion on the Humanoid Robot DURUS 1 Introduction 2 Robot Walking Model 3 Direct Collocation Based HZD Optimization 4 Experimental Validation 5 Methodology Performance 6 Conclusions Acknowledgment References 27 Synthesis of Energy-Bounded Planar Caging Grasps using Persistent Homology 1 Introduction 2 Related Work 3 Definitions and Problem Statement 4 The EBCS-2D Algorithm 5 Experiments 6 Discussion and Future Work References 28 Equilateral Three-Finger Caging of Polygonal Objects Using Contact Space Search 1 INTRODUCTION 2 The Three-Finger Caging Problem 3 Representation of Cages in the Hand’s Configuration Space 4 The Three-Finger Hand Contact Space 5 The Three-Finger Caging Graph 6 The Caging Graph Search Algorithm 7 Conclusion References 29 On the Distinction between Active and Passive Reaction in Grasp Stability Analysis * 1 Introduction 2 Related Work 3 Problem Statement 4 Grasp Model 5 Solution Method 6 Analysis and Results 7 Discussion 8 Conclusions References 30 Robust Planar Dynamic Pivoting by Regulating Inertial and Grip Forces 1 Introduction 2 Related Work 3 Modeling 4 Robust Controller Design 5 Experiments 6 Conclusions and Future Work 7 Acknowledgment References 31 Re-configuring knots to simplify manipulation 1 Introduction 2 Knots and knot geometry 3 Arranging knots 4 Untangling knots 5 Conclusions and future work References 32 Continuous Pseudoinversion of a Multivariate Function: Application to Global Redundancy Resolution 1 Introduction 2 Related work 3 Problem definition 4 Pathwise Redundancy Resolution 5 Approximate global redundancy resolution 6 Interpolation between sample points 7 Results 8 Conclusion Acknowledgment References 33 A Generalized Label Correcting Method forOptimal Kinodynamic Motion Planning 1 Introduction 2 GLC Methods 3 Numerical Experiments 4 Analysis of the GLC Condition 5 Conclusion Acknowledgements References 34 Asymptotically optimal planning under piecewise-analytic constraints 1 Introduction 2 Background and notation 3 Modes and orbits 4 Algorithms 5 Analysis 6 Computational experiments 7 Conclusion Bibliography 35 Decidability of Semi-Holonomic Prehensile Task and Motion Planning 1 Introduction 2 Semi-holonomic task and motion planning framework 3 Decidability result 4 Decision procedure 5 Conclusion References 36 Approximation Algorithms for Time-Window TSP and Prize Collecting TSP Problems 1 Introduction 2 TWTSP and TWPC on a Line 3 General Metric Space 4 Conclusion and Future Work Acknowledgements References 37 Resolution-Exact Planner for Thick Non-Crossing 2-Link Robots* 1 Introduction 2 Configuration Space of Non-Crossing 2-Link Robot 3 Forbidden Angle Analysis of Thick Links 4 Subdivision for Thick Non-Crossing 2-Link Robot 5 Implementation and Experiments 6 Conclusion and Limitations References 38 Fast and Bounded Probabilistic Collision Detection for High-DOF Robots in Dynamic Environments 1 Introduction 2 Related Work 3 Probabilistic Collision Detection for High-DOF Robots 4 Trajectory Optimization using Probabilistic Collision Detection 5 Results 6 Conclusions, Limitations and Future Work 7 Acknowledgments References 39 Efficient Nearest-Neighbor Search for Dynamical Systems with Nonholonomic Constraints 1 Introduction 2 Geometry of Nonholonomic Systems 3 Thek-d tree Data Structure 4 Complexity Analysis 5 The Lie splitting strategy 6 Experimental results 7 Conclusion References 40 Collision detection or nearest-neighbor search? On the computational bottleneck in sampling-based motion planning* 1 Introduction 2 Background and related work 3 The asymptotic behavior of common MP algorithms 4 Nearest-neighbor sensitive settings 5 Asymptotically-optimal motion-planning using R-NN 6 Future work References 41 Dynamic Region-biased Rapidly-exploring Random Trees 1 Introduction 2 Preliminaries and Related Work 3 Dynamic Region RRT 4 Experimental Evaluation 5 Conclusion Acknowledgements References 42 Motion Planning for Reconfigurable Mobile Robots Using Hierarchical Fast Marching Trees 1 Introduction 2 Related Work 3 Problem Formulation and Background 4 Hierarchical Bidirectional Fast Marching Tree 5 Analysis 6 Experiments 7 Conclusions and Future Work References 43 SWIRL: A SequentialWindowed Inverse Reinforcement Learning Algorithm for Robot TasksWith Delayed Rewards 1 Introduction 2 Related Work 3 Problem Statement and Model 4 SequentialWindowed Inverse Reinforcement Learning 5 Experiments 6 Discussion and Future Work References 44 Adapting Deep Visuomotor Representations with Weak Pairwise Constraints 1 Introduction 2 Related work 3 Preliminaries 4 Domain alignment with weakly supervised pairwise constraints 5 Adapting visuomotor control policies 6 Conclusion References 45 Bandit-Based Model Selection for Deformable Object Manipulation 1 Introduction 2 Related Work 3 Problem Statement 4 Bandit-Based Model Selection 5 MABFormulation for Deformable Object Manipulation 6 Experiments and Results 7 Conclusion 8 Acknowledgements References 46 Matrix Completion as a Post-Processing Technique for Probabilistic Roadmaps 1 Introduction 2 Background 3 Algorithm overview 4 Numerical implementation 5 Solution Properties and Errors 6 Results 7 Connections to the Literature and Future Work Acknowledgment References 47 Persistent Surveillance of Events with Unknown Rate Statistics 1 Introduction 2 Problem Definition 3 Methods 4 Analysis 5 Results 6 Conclusion References 48 Planning and Resilient Execution of Policies For Manipulation in Contact with Actuation Uncertainty 1 Introduction 2 Related Work 3 Problem Statement 4 Methods 5 RESULTS 6 Conclusion Acknowledgements References 49 Configuration Lattices for Planar Contact Manipulation Under Uncertainty 1 Introduction 2 Related Work 3 Problem Formulation 4 Configuration Lattice POMDP 5 Online POMDP Planner 6 Experimental Results 7 Discussion Acknowledgements Bibliography 50 On the Effects of Measurement Uncertainty in Optimal Control of Contact Interactions 1 Introduction 2 Problem Formulation and Background Material 3 Algorithm Derivation 4 Experimental Results 5 Discussion 6 Conclusion Acknowledgments. References 51 Feedback Control of the Pusher-Slider System: A Story of Hybrid and Underactuated Contact Dynamics 1 INTRODUCTION 2 RELATED WORK 3 CHALLENGES OF CONTROL THROUGH CONTACT 4 PUSHER-SLIDER SYSTEM 5 MODEL PREDICTIVE CONTROL 6 RESULTS 7 CONCLUSION References 52 Assembling and disassembling planar structures with divisible and atomic components 1 Introduction 2 Computing a lower bound on the number of pieces 3 Computing a sufficient number of pieces 4 Conclusions, limitations, and future work References 53 A BCMP Network Approach to Modeling and Controlling Autonomous Mobility-on-Demand Systems 1 Introduction 2 Background Material 3 Model Description and Problem Formulation 4 Asymptotically Optimal Algorithms for AMoD routing 5 Numerical Experiments 6 Conclusions References 54 Optimal Policies for Platooning and Ride Sharing in Autonomy-Enabled Transportation 1 Introduction 2 Problem Setup 3 General Results 4 On Pareto-optimal Regular Policies 5 On Pareto-optimal Time-table Policies 6 Discussion and Conclusion Acknowledgements References 55 Decentralised Monte Carlo Tree Search for Active Perception 1 Introduction 2 Related work 3 Problem statement 4 Dec-MCTS 5 Analysis 6 Experiments: Generalised team orienteering 7 Experiments: Active object recognition 8 Discussion and future work Acknowledgements. References 56 Decentralized Multi-Agent Navigation Planning with Braids 1 Introduction 2 Related Work 3 Foundations 4 Planning Global Joint Strategies with Braids 5 Algorithm Design 6 Application 7 Discussion and Future Work Acknowledgement Bibliography 57 A Geometric Approach for Multi-Robot Exploration in Orthogonal Polygons 1 Introduction 2 Related Work 3 Multi-Robot Exploration Algorithm 4 Adapting to Real-World Scenarios 5 Simulations 6 Experiments 7 Conclusion References 58 Assignment Algorithms for Variable Robot Formations 1 Introduction 2 Background: Assignment Problems 3 Finding Optimal Assignments and Scaled Goal Formations: An LBAP Formulation 4 Incremental Updates to Compute the Optimal LBAP 5 Finding Optimal Translated Goal Formations 6 Related Work 7 Conclusion References Author Index