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(Herausgeber*in)

Springer (Verlag)

1. Auflage

Erschienen am 8. Februar 2021

XIII, 568 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

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

287,83 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken