Algorithmic Foundations of Robotics XIV

Name: Algorithmic Foundations of Robotics XIV | Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics
Brand: Springer
Price: 287.83 EUR
Availability: OnlineOnly

Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics

Steven M. Lavalle Ming Lin Timo Ojala Dylan Shell Jingjin Yu(Editor)

Springer (Publisher)

1st Edition

Published on 8. February 2021

XIII, 568 pages

E-Book

PDF with digital watermarking

System requirements

978-3-030-66723-8 (ISBN)

€287.83incl. 7% vat

System requirements

for PDF with digital watermarking

E-Book Single Licence

Available for download

Description

More details

Other 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

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Algorithmic Foundations of Robotics XIV

Description

More details

Other editions

Additional editions

Content

System requirements