
Algorithmic Foundations of Robotics XIV
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
This proceedings book helps bring insights from this array of technical sub-topics together, as advanced robot algorithms draw on the combined expertise of many fields-including control theory, computational geometry and topology, geometrical and physical modeling, reasoning under uncertainty, probabilistic algorithms, game theory, and theoretical computer science. Intelligent robots and autonomous systems depend on algorithms that efficiently realize functionalities ranging from perception to decision making, from motion planning to control. The works collected in this SPAR book represent the state of the art in algorithmic robotics. They originate from papers accepted to the 14th International Workshop on the Algorithmic Foundations of Robotics (WAFR), traditionally a biannual, single-track meeting of leading researchers in the field of robotics. WAFR has always served as a premiere venue for the publication of some of robotics' most important, fundamental, and lasting algorithmic contributions, ensuring the rapid circulation of new ideas. Though an in-person meeting was planned for June 15-17, 2020, in Oulu, Finland, the event ended up being canceled owing to the infeasibility of international travel during the global COVID-19 crisis.
More details
Other editions
Additional editions

Content
- Intro
- Foreword
- Preface
- Contents
- ABC-LMPC: Safe Sample-Based Learning MPC for Stochastic Nonlinear Dynamical Systems with Adjustable Boundary Conditions
- 1 Introduction
- 2 Related Work
- 3 Problem Statement
- 4 Preliminaries
- 4.1 Safe Set
- 4.2 Value Function
- 4.3 Transfer to Novel Goal Sets
- 5 Controller Design
- 5.1 Task Driven Optimization
- 5.2 Start State Expansion
- 6 Properties of ABC-LMPC
- 7 Practical Implementation
- 7.1 Sample-Based Safe Set
- 7.2 Start State Expansion Strategy
- 7.3 Goal Set Transfer
- 7.4 ABC-LMPC Optimization Procedure
- 8 Experiments
- 8.1 Experimental Domains
- 8.2 Fixed Start and Goal Conditions
- 8.3 Start State Expansion
- 8.4 Goal Set Transfer
- 8.5 Inverted Pendulum Swing-Up Task
- 9 Discussion and Future Work
- References
- Inferring Obstacles and Path Validity from Visibility-Constrained Demonstrations
- 1 Introduction
- 2 Related Work
- 3 Preliminaries
- 3.1 Demonstrator's Problem
- 3.2 Obstacles and Obstacle Vertices
- 3.3 Verifying Environment Configurations
- 4 Problem Statement
- 5 Method
- 5.1 Probabilistically Complete Obstacle Sampling
- 5.2 Analysis of Algorithm 1
- 5.3 Heuristic-Guided Obstacle Sampling
- 5.4 Applications in Planning and Scouting
- 6 Experimental Results
- 6.1 Single Candidate
- 6.2 Evaluation of Many Candidates
- 6.3 Sequential Demonstrations and Prob- Abilistic Environment Representation
- 7 Conclusion
- References
- Space-Aware Reconfiguration
- 1 Introduction
- 2 Labeled Version: Analysis of the Translation Plane
- 3 Labeled Version: Space-Aware Optimization
- 4 Unlabeled Version: Preliminary Analysis
- 5 Unlabeled Version: Space-Aware Practical Solutions
- 5.1 Heuristics for Short Valid Translations
- 5.2 Bounding the Heuristic Solutions
- 5.3 Implementation of the Heuristic Algorithm
- 6 Further Research
- References
- Evasive Navigation of an Autonomous Mobile Robot in Hostile Unknown Environments
- 1 Introduction
- 2 The On-line Evasive Navigation Problem
- 3 Optimal Evasive Off-line Navigation
- 4 The On-line Evasive Navigation Algorithm
- 5 Competitive Upper Bound on the E-Nav Algorithm
- 5.1 Upper Bound on the Robot On-line Path Length
- 5.2 Competitive Bound on E-Nav
- 6 Conclusion
- References
- Neural Collision Clearance Estimator for Batched Motion Planning
- 1 Introduction
- 2 Related Work
- 3 Problem Statement
- 4 Methodology
- 4.1 ClearanceNet
- 4.2 CN-RRT: Sampling-Based Planning with ClearanceNet
- 5 Results
- 5.1 ClearanceNet Results
- 5.2 CN-RRT Results
- 6 Analysis and Discussion
- 7 Conclusions
- References
- Cover Combinatorial Filters and Their Minimization Problem
- 1 Introduction
- 2 Preliminary Definitions and Problem Description
- 2.1 P-Filters and Their Minimization
- 2.2 Complexity of P-Filter Minimization Problems
- 3 Related Work: Prior Filter Minimization Ideas (so-fm)
- 4 A New Graph Problem that Is Equivalent to so-fm
- 4.1 A New Minimum Clique Cover Problem
- 4.2 From Minimal Clique Covers to Filters
- 4.3 Correspondence of mcczc and so-fm Solutions
- 5 Generalizing to mo-fm
- 6 Reduction from mcczc and gmczc to SAT
- 7 Experimental Results
- 8 Conclusion
- References
- Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency
- 1 Introduction
- 2 Problem Definition
- 3 Approximation Algorithms in a General Metric
- 4 Sites in R1
- 5 Conclusion and Future Work
- References
- Locally-Connected Interrelated Network: A Forward Propagation Primitive
- 1 Introduction
- 2 Background and Related Work
- 2.1 Background
- 2.2 Related Work
- 3 LCI-Net
- 3.1 Representing Transition Function
- 3.2 Propagating Information
- 3.3 Complexity Analysis
- 4 Applying LCI-Net
- 4.1 Application to the Planning Component
- 4.2 Application to the Belief Update Component
- 5 Experiments
- 5.1 Experimental Setup
- 5.2 Results and Discussion
- 6 Summary
- References
- Optimized Synthesis of Snapping Fixtures
- 1 Introduction
- 1.1 Background
- 1.2 Our Results
- 1.3 Outline
- 2 Terminology and Properties
- 2.1 Fixture Structure
- 2.2 The Configuration Space
- 2.3 Spreading Degree
- 2.4 Fixture Planning
- 2.5 Properties
- 3 Algorithm
- 4 Two Applications
- 4.1 Minimal Weight Fixtures
- 4.2 Minimal Obscuring Fixtures
- 4.3 3D Printing Considerations
- 5 Experimental Results
- References
- Sampling-Based Motion Planning for Uncertain High-Dimensional Systems via Adaptive Control
- 1 Introduction
- 2 Problem Formulation
- 3 Main Results
- 3.1 Control Design
- 3.2 Motion Planner
- 3.3 Collision Checking in free(tr,r)
- 4 Experimental Results
- 5 Discussion
- References
- Every Action-Based Sensor
- 1 Introduction
- 1.1 Broader Motivation
- 2 Preliminaries
- 2.1 Scope
- 3 What It Means to Make Progress: The Progress Measure
- 3.1 Lack of Uniqueness in Progress Measures and Crossovers
- 4 Removing Crossovers and Enumerating Progress Measures
- 5 Translating Progress Measures into Sensors
- 6 Example
- 7 Completeness
- 8 Conclusion
- References
- Linear-Time Variational Integrators in Maximal Coordinates
- 1 Introduction
- 2 Background
- 2.1 Quaternions
- 2.2 Articulated Rigid Body
- 3 Variational Integrator
- 3.1 Translational Component
- 3.2 Rotational Component
- 4 Linear-Time Sparse Solver
- 4.1 Newton's Method and Dense LDU Decomposition
- 4.2 Sparse Factorization and Back-Substitution
- 4.3 Extension to Closed-Loop Mechanisms
- 5 Experiments and Comparison
- 5.1 Energy Conservation, No Constraint Drift, and Linear Time
- 5.2 Performance Comparison
- 6 Conclusion
- References
- Information Requirements of Collision-Based Micromanipulation
- 1 Introduction
- 1.1 Background and Related Work
- 2 Model and Definitions
- 2.1 Primitives and Robots
- 2.2 Information Spaces
- 2.3 Robot Dominance
- 3 Manipulating a Cart in a Long Corridor
- 4 A Formal Comparison of Several Robot Designs
- 4.1 Robot 0: Omniscient and Omnipotent
- 4.2 Robot 1: Complex
- 4.3 Robot 2: Simple
- 4.4 Robot 3: Minimal
- 4.5 Comparing Robots
- 5 Feasibility and Dynamics of Cyclic Motion Strategies
- 6 Conclusion
- 6.1 Future Directions
- References
- Characterizing Marginalization and Incremental Operations on the Bayes Tree
- 1 Introduction
- 2 Problem Formulation and Background
- 3 Related Work
- 4 Method
- 4.1 General Inference Using the Bayes Tree
- 4.2 Characterizing Marginalization on the Bayes Tree
- 4.3 Chapman-Kolmogorov and Generalized Belief Propagation
- 4.4 Clique Recycling Strategies
- 5 Experimental Results
- 5.1 Simulation: Circular Example
- 5.2 Manhattan World Dataset
- 6 Conclusions
- References
- Synchronized Multi-arm Rearrangement Guided by Mode Graphs with Capacity Constraints
- 1 Introduction
- 2 Related Work
- 3 Problem Setup and Terminology
- 3.1 Modeling Choices and Assumptions
- 4 Mode Graph with Capacity Constraints
- 5 Integer Linear Program for MAPF on Mode Graph
- 6 Integrated Task and Motion Planning
- 6.1 Algorithm
- 7 Results
- 8 Discussion
- References
- Hierarchical Multiobjective Shortest Path Problems
- 1 Introduction
- 2 Shortest Path Problem on Directed Graphs with Cumulative Algebraic Costs
- 3 Multicost GSPP and Failure of Classical Algorithms
- 4 Optimal Subgraph
- 5 Regular Cost Monoids
- 6 Iterated Algorithm for Regular Multicost GSPP
- 7 Summary
- References
- Planning to Chronicle
- 1 Motivation and Introduction
- 2 Related Work
- 3 The Problem
- 3.1 Events and Observations
- 3.2 Story Specifications, Belief States, and Policies
- 3.3 Optimal Recording Problems
- 4 Algorithm Description
- 4.1 The Goal POMDP
- 4.2 Solving the Goal POMDP
- 4.3 Solving Rtm/Fom via Goal MDP
- 5 Representation-Invariance of Expected Time
- 6 Construction of Specification Languages
- 6.1 Multiple Recipients
- 6.2 Mistakes Were Made
- 6.3 At Least One Good Shot
- 7 Case Studies
- 7.1 Turisti Oulussa
- 7.2 Wedding Reception
- 8 Conclusions and Future Work
- References
- Deadlock Analysis and Resolution for Multi-robot Systems
- 1 Introduction
- 2 Prior Work
- 2.1 Prior Work on Avoidance Control
- 2.2 Prior Work on Deadlock Resolution
- 3 Avoidance Control with CBFs: Review
- 4 Analysis of N Robot Deadlock
- 4.1 KKT Conditions
- 4.2 KKT Conditions for the Deadlock Case
- 4.3 Graph Enumeration Based Complexity Analysis of Deadlock
- 5 Two-Robot Deadlock
- 5.1 Characteristics of Two-Robot Deadlock
- 6 Three Robot Deadlock
- 7 Deadlock Resolution
- 8 Conclusions
- References
- Imitation Learning as f-Divergence Minimization
- 1 Introduction
- 2 Related Work
- 3 Problem Formulation
- 4 Framework for Divergence Minimization
- 4.1 Variational Approximation of Divergence
- 4.2 Recovering Existing Imitation Learning Algorithms
- 4.3 Alternate Techniques for Reverse KL Minimization via Interactive Learning
- 5 Multi-modal Trajectory Demonstrations
- 6 Experiments
- 6.1 Low Dimensional Tasks
- 6.2 High Dimensional Continuous Control Task
- 7 Discussion
- References
- Approximation Algorithms for Distributed Multi-robot Coverage in Non-convex Environments
- 1 Introduction
- 2 Continuous and Discrete Coverage Problems
- 2.1 Continuous Environment
- 2.2 Discrete Environment
- 3 From a Continuous to a Discrete Problem
- 4 Distributed Algorithm on Graphs
- 4.1 High-Level Idea
- 4.2 Detailed Description
- 5 Analysis of the Algorithm
- 5.1 Correctness and Approximation Factor
- 6 Simulation Results
- 6.1 Convex Environments
- 6.2 Non-convex Environments
- 7 Conclusion
- References
- The Surprising Effectiveness of Linear Models for Visual Foresight in Object Pile Manipulation
- 1 Introduction
- 2 Problem Statement
- 2.1 Setup and Notation
- 2.2 A Simple Lyapunov-Based Controller
- 3 Models for Image Prediction
- 3.1 Switched-Linear Model
- 3.2 Deep-Learning Model
- 3.3 Object-Centric Transport Model
- 4 Simulation Results
- 4.1 Switched-Linear Model
- 4.2 Comparison of Visual Prediction
- 4.3 Closed-Loop Performance
- 5 Experiment Results
- 6 Conclusion
- References
- Forward Chaining Hierarchical Partial-Order Planning
- 1 Introduction
- 2 Background
- 3 Forward Chaining with Partial-Order Planning (FCPOP)
- 4 Forward Chaining with Hierarchical Partial-Order Planning
- 5 Evaluation
- 6 Discussion
- References
- Learning Control Sets for Lattice Planners from User Preferences
- 1 Introduction
- 1.1 Related Work
- 1.2 Contributions
- 2 Problem Statement
- 2.1 Preliminaries
- 2.2 Problem Formulation
- 3 Approach
- 3.1 User Model
- 3.2 Estimation of the Loss Function
- 3.3 Main Results
- 3.4 Computational Complexity
- 3.5 Computing an Optimal Control Set
- 4 Evaluation
- 4.1 Training Error
- 4.2 Test Error
- 5 Discussion
- References
- Active Localization of Multiple Targets from Noisy Relative Measurements
- 1 Introduction
- 2 Related Work and Contributions
- 2.1 Sensor Placement
- 2.2 Active Target Localization
- 2.3 Active Target Tracking
- 2.4 Statement of Contributions
- 3 Preliminaries
- 3.1 Uncertainty Measures
- 3.2 Reinforcement Learning
- 4 Problem Statement
- 5 Method
- 5.1 Representing the Observations
- 5.2 Learning Target Localization
- 6 Analysis
- 6.1 Offline Trajectory Optimization
- 6.2 Localizing Static Targets
- 6.3 Localizing Dynamic Targets
- 6.4 Generalization Performance
- 7 Conclusion
- References
- Experiments with Tractable Feedback in Robotic Planning Under Uncertainty: Insights over a Wide Range of Noise Regimes
- 1 Introduction
- 1.1 Related Work
- 2 Problem Formulation
- 2.1 System Model
- 2.2 Stochastic Optimal Control Problem
- 3 A Decoupling Principle
- 3.1 Near-Optimal Decoupling in Stochastic Optimal Control
- 3.2 Multi-agent Setting
- 3.3 Planning Complexity Versus Uncertainty
- 4 The Planning Algorithms
- 4.1 Deterministic Optimal Control Problem
- 4.2 Model Predictive Control (MPC)
- 4.3 Short Horizon MPC (MPC-SH)
- 4.4 Trajectory Optimised Linear Quadratic Regulator (T-LQR)
- 4.5 T-LQR with Replanning (T-LQR2)
- 4.6 Multi-agent Versions
- 5 Simulation Results
- 5.1 Single Agent Setting
- 5.2 Multi-agent Setting
- 5.3 Definition of Noise Regimes and Discussion of the Results
- 6 Conclusions and Implications
- References
- Back-Propagation Through Signal Temporal Logic Specifications: Infusing Logical Structure into Gradient-Based Methods
- 1 Introduction
- 2 Preliminaries
- 2.1 Signals
- 2.2 Signal Temporal Logic: Syntax and Semantics
- 2.3 Graphical Structure of STL Formulas
- 3 STL Robustness Formulas as Computation Graphs
- 3.1 Computation Graphs
- 3.2 Computation Graphs of STL Operators
- 3.3 Calculating Robustness with Computation Graphs
- 3.4 Smooth Approximations to stlcg
- 4 Case Studies: Using stlcg for Robotics Applications
- 4.1 Motion Planning with STL Constraints
- 4.2 Parametric STL for Behavioral Clustering
- 4.3 Robustness-Aware Neural Networks
- 5 Future Work and Conclusions
- References
- Hybrid Control for Learning Motor Skills
- 1 Introduction
- 2 Background
- 3 Hybrid Learning
- 3.1 Deterministic
- 3.2 Stochastic
- 4 Results
- 5 Conclusion
- References
- Pushing the Boundaries of Asymptotic Optimality in Integrated Task and Motion Planning
- 1 Motivation
- 2 Integrated Task and Motion Planning
- 2.1 Asymptotic Optimality of Sampling-Based Algorithms
- 2.2 Algorithmic Outline: Forward Search Tree over Orbital Roadmaps
- 3 Summary of Previous Results: FOBT
- 4 New Arguments in Integrated Task and Motion Planning
- 5 Model for Approaching Boundaries
- 5.1 Cone Condition
- 5.2 Robust Clearance for Boundary Paths
- 6 Discussion
- References
- Efficient Contact Mode Enumeration in 3D
- 1 Introduction
- 2 Related Work
- 3 Kinematics of Contact
- 3.1 Rigit Body Transformation
- 3.2 Contact Normal Velocity
- 3.3 Contact Tangent Velocity Approximation
- 4 Convex and Combinatorial Geometry
- 4.1 Convex Polytopes
- 4.2 Hyperplane Arrangements
- 4.3 Face Lattice
- 4.4 Polarity
- 4.5 Zonotopes
- 5 Contact Mode Enumeration in 3D
- 5.1 Contacting/Separating Mode Enumeration
- 5.2 Sticking/Sliding Mode Enumeration
- 5.3 Full Mode Enumeration
- 6 Results
- 7 Related Applications
- 8 Conclusion
- References
- Visualizing Local Minima in Multi-robot Motion Planning Using Multilevel Morse Theory
- 1 Introduction
- 2 Related Work
- 2.1 Multi-robot Motion Planning
- 2.2 Multi-path Multi-robot Motion Planning
- 3 Foundations
- 3.1 Morse Theory
- 3.2 Multilevel Abstractions Using Fiber Bundles
- 3.3 Local-Minima Tree for Multilevel Morse Theory
- 4 Multi-robot Motion Explorer
- 5 Demonstrations
- 6 Conclusion
- References
- On Rearrangement of Items Stored in Stacks
- 1 Introduction
- 2 Lower Bounds for Stack Rearrangement
- 3 The Rubik Table Problem
- 4 Tighter Upper Bounds for Stack Rearrangement
- 4.1 Linear Step Algorithm for LSR with d n
- 4.2 Linear Step Algorithm for LSR with d = nm2 and Constant m
- 4.3 Constant n or d
- 5 Conclusion and Discussion
- References
- Approximation Algorithms for the Single Robot Line Coverage Problem
- 1 Introduction
- 2 Related Work
- 3 The Single Robot Line Coverage Problem
- 3.1 Preliminaries
- 4 Graphs with All Required Edges
- 4.1 Integer Programming Formulation
- 4.2 An Alternative Formulation
- 4.3 A Network Flow Graph Model
- 4.4 Eulerian Graphs with All Required Edges
- 4.5 A 2-Approximation Algorithm for General Graphs with All Required Edges
- 5 Rural Graphs
- 5.1 Rural Graphs with a Single Connected Component
- 5.2 Rural Graphs with Multiple Connected Components
- 6 Conclusion
- References
- Scalable Low-Rank Semidefinite Programming for Certifiably Correct Machine Perception
- 1 Introduction
- 2 Problem Formulation
- 3 Low-Rank Semidefinite Programming
- 3.1 Ensuring Optimality
- 3.2 Restoring Feasibility
- 3.3 The Complete Algorithm
- 4 Experimental Evaluation
- 4.1 Experimental Problem Formulation
- 4.2 Implementation and Results
- 5 Conclusion
- References
- Author Index
System requirements
File format: PDF
Copy protection: Watermark-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Use the free software Adobe Reader, Adobe Digital Editions, or any other PDF viewer of your choice (see eBook Help).
- Tablet/Smartphone (Android; iOS): Install the free app Adobe Digital Editions or another reading app for eBooks, e.g., PocketBook (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (only limited: Kindle).
The file format PDF always displays a book page identically on any hardware. This makes PDF suitable for complex layouts such as those used in textbooks and reference books (images, tables, columns, footnotes). Unfortunately, on the small screens of e-readers or smartphones, PDFs are rather annoying, requiring too much scrolling.
This eBook uses Watermark-DRM, a „soft” copy protection. This means that there are no technical restrictions to prevent illegal distribution. However, there is a personalised watermark embedded in the eBook that can be used to identify the purchaser of the eBook in the event of misuse and to provide evidence for legal purposes.
For more information, see our eBook Help page.