Algorithmic Foundations of Robotics XIII

Name: Algorithmic Foundations of Robotics XIII | Proceedings of the 13th Workshop on the Algorithmic Foundations of Robotics
Brand: Springer
Price: 213.99 EUR
Availability: OnlineOnly

Proceedings of the 13th Workshop on the Algorithmic Foundations of Robotics

Marco Morales Lydia Tapia Gildardo Sánchez-Ante Seth Hutchinson(Editor)

Springer (Publisher)

1st Edition

Published on 7. May 2020

XXII, 959 pages

E-Book

PDF with digital watermarking

System requirements

978-3-030-44051-0 (ISBN)

€213.99incl. 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
Organization
Co-chairs
Steering Committee
Advisory Committee
Program Committee
Additional Reviewers
Session Chairs and Respondents
Sponsoring Institutions
Contents
General Tools for Motion Planning
Path Planning for Ellipsoidal Robots and General Obstacles via Closed-Form Characterization of Minkowski Operations
1 Introduction
2 Mathematical Preliminaries
2.1 Minkowski Sum and Difference Between Two Convex Objects
2.2 Closed-Form Minkowski Operations Between an Ellipsoid and a General Convex Differentiable Surface Embedded in Rn
2.3 Explicit Expressions of the Closed-Form Minkowski Operations Between an Ellipse and a Superellipse
3 The Highway RoadMap Path Planning Algorithm for Ellipsoidal Robots: Reviews and Extensions
3.1 Overview of the Highway RoadMap Algorithm
3.2 A Sweep-Line Process for the Cell Decomposition Within One C-Layer
3.3 A Local Planner for Vertex Connections Between C-Layers
4 Experiments on Path Planning for a 2D Elliptical Robot
4.1 Experimental Parameters
4.2 Collision Checking Methods for the Sample-Based Algorithms
4.3 Experimental Results
4.4 Discussion
5 Conclusion
References
Free Space of Rigid Objects: Caging, Path Non-existence, and Narrow Passage Detection
1 Introduction
2 Related Work
3 Free Space Decomposition
4 Theoretical Properties of Our Approach
5 Examples and Experiments
6 Conclusion
References
Fast Collision Detection for Motion Planning Using Shape Primitive Skeletons
1 Introduction
2 Related Work
2.1 Bounding Volume Hierarchies
2.2 Inner Volume Approximations
2.3 Workspace Certificates
3 Fast Collision Detection
4 Shape Primitive Skeleton Construction
4.1 Topological Skeleton for Shape Primitive Placement
4.2 Shape Primitive Placement
5 Results
5.1 Shape Primitive Skeleton and Coverage
5.2 Impact on Collision Detectors
5.3 Use of Skeletons of both Spaces
5.4 Performance with Different Robot Sizes
6 Conclusion
References
Fast Swept Volume Estimation with Deep Learning
1 Introduction
2 Related Work
3 Methods
3.1 Training Dataset Generation
3.2 Training Weighted Euclidean Distance Estimator, Dsvwe
3.3 Training Deep Swept Volume Distance Estimator, Dsvdnn
3.4 Hierarchical Neighbor Search, HNS
4 Swept Volume Properties
5 Evaluations
5.1 Learning Results
5.2 Planning Results
6 Distance Metric Trade-Offs
7 Conclusion
References
Concurrent Nearest-Neighbor Searching for Parallel Sampling-Based Motion Planning in SO(3), SE(3), and Euclidean Spaces
1 Introduction
2 Related Work
3 Problem Definition
4 Method
4.1 Data Storage
4.2 Inserting Data
4.3 Searching Operations
5 Correctness and Analysis
6 Results
7 Conclusion
References
Data Structures for Motion Planning
A Visibility-Based Approach to Computing Nondeterministic Bouncing Strategies
1 Introduction
2 Related Work
3 Model and Definitions
4 Visibility-Based Boundary Partitioning
5 Safe Actions
6 Dynamical Properties of Paths
7 Applications
7.1 Navigation
7.2 Patrolling
8 Open Questions and Future Work
References
Finding Plans Subject to Stipulations on What Information They Divulge
1 Introduction
1.1 Contributions and Itinerary
2 Related Work
3 The Model: Worlds, Robots and Observers
3.1 P-Graph and Its Interaction Language
3.2 Planning Problems and Plans
3.3 Information Disclosure Policy, Divulged Plan, and Observer
3.4 Information Stipulations
4 The Observer's Knowledge of the Robot's Plan
5 Searching for Plans and Disclosure Policy: The Seek problems
5.1 Finding a Plan Given Some Predetermined D
5.2 Search for Plan and Label Map for the Finest Observer, Disclosing the Same
6 Experimental Results
7 Conclusion
References
Planning Under Uncertainty
Online Partial Conditional Plan Synthesis for POMDPs with Safe-Reachability Objectives
1 Introduction
2 Problem Formulation
3 Online Partial Conditional Plan Synthesis
3.1 Partial Conditional Plan Generation
4 Experiments
5 Discussion
References
An Approximation Algorithm for Risk-Averse Submodular Optimization
1 Introduction
2 Background and Preliminaries
2.1 Risk Measures
3 Problem Formulation and Case Studies
3.1 Problem Formulation
3.2 Case Studies
4 Algorithm and Analysis
4.1 Sequential Greedy Algorithm
4.2 Performance Analysis of SGA
5 Simulations
5.1 Resilient Mobility-on-Demand Under Arrival Time Uncertainty
5.2 Robust Environment Monitoring
6 Conclusion and Discussion
References
Pushing Fast and Slow: Task-Adaptive Planning for Non-prehensile Manipulation Under Uncertainty
1 Introduction
2 Problem Formulation
3 Proposed Approach
4 Generating a Variety of Actions
5 Trajectory Optimization
6 Baseline Approach
7 Experiments
7.1 Push Planning Simulation Experiments
7.2 Grasping in Clutter Simulation Experiments
7.3 Real Robot Experiments
8 Related Work
9 Discussion and Future Work
References
Imitation Learning
Learning Stabilizable Dynamical Systems via Control Contraction Metrics
1 Introduction
2 Review of Contraction Theory
2.1 Control Contraction Metrics
3 Problem Formulation
4 Solution Formulation
4.1 Sparsity of Input Matrix Estimate
4.2 Finite-Dimensional Optimization
5 Solution Algorithm
6 Experimental Results
6.1 Generation of Datasets
6.2 Models
6.3 Validation and Comparison
7 Conclusions
References
Generalizing Robot Imitation Learning with Invariant Hidden Semi-Markov Models
1 Introduction
1.1 Related Work
2 Hidden Markov Models
2.1 Encoding with HSMM
2.2 Decoding from HSMM
2.3 Motion Generation with Linear Quadratic Tracking
3 Invariant Task-Parameterized HSMMs
3.1 Model Learning
3.2 Model Adaptation in New Situations
4 Latent Space Representations
4.1 Mixture of Factor Analyzers
4.2 Semi-tied Mixture Model
4.3 Bayesian Non-parametrics Under Small Variance Asymptotics
5 Experiments, Results and Discussion
6 Conclusions
References
A Dynamic Regret Analysis and Adaptive Regularization Algorithm for On-Policy Robot Imitation Learning
1 Introduction
2 Preliminaries
3 Related Work
4 On-Policy Algorithms
4.1 DAGGER
4.2 Imitation Gradient and Multiple Imitation Gradient
5 Dynamic Regret
6 Main Results
6.1 DAGGER
6.2 Imitation Gradient
6.3 Multiple Imitation Gradient
7 Adaptive On-Policy Regularization
8 Empirical Evaluation
8.1 Cart-Pole Balancing
8.2 Walker Locomotion
9 Discussion and Future Work
References
Learning Constraints from Demonstrations
1 Introduction
2 Related Work
3 Preliminaries and Problem Statement
3.1 Forward Optimal Control Problem
3.2 Inverse Constraint Learning Problem
4 Method
4.1 Trajectories Satisfying Known Constraints
4.2 Sampling Trajectories Satisfying Known Constraints
4.3 Improving learnability using cost function structure
4.4 Integer Program Formulation
4.5 Bounded Suboptimality of Demonstrations
5 Analysis
5.1 Learnability
5.2 Conservativeness
6 Evaluations
7 Conclusion
References
Probability-Weighted Temporal Registration for Improving Robot Motion Planning and Control Learned from Demonstrations
1 Introduction
2 Related Work
3 Problem Definition
4 Method
4.1 Dynamic Time Warping as a Graph Algorithm
4.2 Temporal Registration Using the Viterbi Algorithm
4.3 PTR Using the Forward-Backward Algorithm
4.4 Non-degenerate Temporal Registration
5 Application to Robot Learning from Demonstrations
6 Results
6.1 PTR Applied to the van den Berg et al. Method
6.2 PTR Applied to the Bowen et al. Method
7 Conclusion
References
Learning in Planning
SACBP: Belief Space Planning for Continuous-Time Dynamical Systems via Stochastic Sequential Action Control
1 Introduction
1.1 Related Work in Belief Space Planning
1.2 Contributions
2 SACBP Algorithm
2.1 Problems with Mixed Observability
2.2 General Belief Space Planning Problems
2.3 Closed-Loop Nominal Policy
2.4 Computational Time Analysis
3 Simulation Results
3.1 Active Multi-target Tracking with Range-Only Observations
3.2 Object Manipulation Under Model Uncertainty
4 Conclusions and Future Work
References
Active Area Coverage from Equilibrium
1 Introduction
2 Related Work
3 Problem Statement
4 Algorithm
5 Simulated Examples
6 Conclusion
References
Learning a Spatial Field with Gaussian Process Regression in Minimum Time
1 Introduction
2 Related Work
2.1 Stationary Sensor Placement
2.2 Mobile Sensing
3 Problem Formulation
4 Algorithm
4.1 Useful Properties of GPs
4.2 Necessary and Sufficient Conditions
4.3 Placement of Sensors for Problem 1
4.4 Finding Optimal Trajectory for Problem 2
5 Simulations
6 Conclusion
References
Meta-learning Priors for Efficient Online Bayesian Regression
1 Introduction
2 Problem Formulation
3 Bayesian Regression
4 Approach
4.1 Algorithmic Preliminaries
4.2 ALPaCA Overview
5 Related Work
6 Experiments
6.1 Toy Experiments
6.2 Dynamical Systems
6.3 Vehicle Lane Change
7 Discussion and Conclusions
References
Deep BOO! Automating Beam Orientation Optimization in Intensity-Modulated Radiation Therapy
1 Introduction
2 Methods and Materials
2.1 Notations and Definitions
2.2 Data Preprocessing
2.3 Neural Network Architecture
2.4 Fluence Map Optimization
2.5 Game Tree Simulation
2.6 Self-play Neuro-Dynamic Programming
3 Results
4 Conclusions
References
Sensor-Based Planning, Navigation, and Control
Continuous Optimization Framework for Depth Sensor Viewpoint Selection
1 Introduction
2 Related Work
3 Methodology
3.1 Angular Terms of Objective Function
3.2 Distance Term of Objective Function
3.3 Objective Function
3.4 Camera Field of View Constraint
3.5 Optimization Approach
4 Evaluation
5 Conclusions
A Appendix
References
Look Before You Sweep: Visibility-Aware Motion Planning
1 Introduction
2 Related Work
3 Definitions
4 Planning Algorithms
4.1 Belief-Space Search
4.2 Local-Visibility Searches
4.3 Tree-Visibility Tour
4.4 Visibility Preimage Backchaining
5 Experiments
6 Discussion
References
Path Planning for Information Gathering with Lethal Hazards and No Communication
1 Introduction
2 Related Work
3 Nomenclature
4 Bayesian Belief Updates and Expected Information Gain
4.1 Target Updates (Assuming a Standard Sensor)
4.2 Hazard Updates (Assuming a Path-Based Sensor)
5 Formal Problem Definitions
6 Algorithms
7 Experiments
8 Summary and Conclusion
References
Reactive Navigation in Partially Known Non-convex Environments
1 Introduction
1.1 Motivation and Prior Work
1.2 Contributions and Organization of the Paper
2 Problem Formulation
3 Multi-layer Representation of the Environment and Its Associated Transformations
3.1 Description of Planning Layers
3.2 Description of the C Switches
3.3 Description of the Star Deforming Factors
3.4 The Map Between the Mapped and the Model Layer
4 Reactive Controller
4.1 Reactive Controller for Fully Actuated Robots
4.2 Reactive Controller for Differential Drive Robots
5 Numerical Experiments
5.1 Comparison with Original Doubly Reactive Algorithm
5.2 Navigation in a Cluttered Non-convex Environment
5.3 Navigation Among Mixed Star-Shaped and Convex Obstacles
6 Conclusion and Future Work
References
Resource-Aware Algorithms for Distributed Loop Closure Detection with Provable Performance Guarantees
1 Introduction
2 Problem Statement
3 Modular Performance Metrics
4 Submodular Performance Metrics
5 Experimental Results
5.1 Certifying Near-Optimality via Convex Relaxation
5.2 Results with Modular Objectives
5.3 Results with Submodular Objectives
6 Conclusion
References
Dynamics of Contact in Manipulation and Locomotion
RMPflow: A Computational Graph for Automatic Motion Policy Generation
1 Introduction
2 Motion Generation and Control
2.1 Motion Policies and the Geometry of Motion
3 Automatic Motion Policy Generation with RMPflow
3.1 Structured Task Maps
3.2 Riemannian Motion Policies (RMPs)
3.3 RMP-tree
3.4 RMP-algebra
3.5 Algorithm: Motion Policy Generation
3.6 Example RMPs
4 Theoretical Analysis of RMPflow
4.1 Geometric Dynamical Systems (GDSs)
4.2 Closure
4.3 Stability
4.4 Invariance
4.5 Related Approaches
5 Experiments
5.1 Controlled Experiments
5.2 System Experiments
6 Conclusion
References
Dynamic Model of Planar Sliding
1 Introduction
2 Related Work
3 Dynamics of Bodies in Contact
4 Equations of Motion for Planar Sliding
4.1 Newton-Euler Equations for Planar Sliding
4.2 Expressions for the ECP
4.3 Friction Model
4.4 Continuous Time Dynamic Model for Planar Sliding
4.5 Discrete-Time Dynamic Model
5 Closed Form Equations for Planar Sliding Motion
6 Numerical Results
7 Conclusions
References
A Constrained Kalman Filter for Rigid Body Systems with Frictional Contact
1 Introduction
2 Related Work
3 Background
3.1 Contact Constraints
3.2 Constrained Kalman Filter
4 Contact Constrained Kalman Filter
4.1 Quadratic Program with Complementarity Constraints
5 Results
5.1 Simulated Data
5.2 Planar Pushing Dataset
5.3 State Estimation for a Biped
6 Conclusion
References
A Quasi-static Model and Simulation Approach for Pushing, Grasping, and Jamming
1 Introduction
2 Related Work
3 Background
3.1 Linear Complementarity Problems
3.2 Friction at Point Contacts Between Object and Manipulator
3.3 Friction at Contact Between Object and Surface
3.4 Friction Behavior as an LCP
4 Finite Velocity Feedback Quasi-statics
5 Time-Stepping Scheme
6 Examples
6.1 Pushing with Two Fingers
6.2 Polygonal Peg-in-hole
6.3 Comparison to Full Dynamics
7 Discussion and Future Work
References
GP-SUM. Gaussian Process Filtering of non-Gaussian Beliefs
1 Introduction
2 Related Work
3 Background on Gaussian Process Filtering
3.1 Bayes Filters
3.2 Gaussian Processes
4 GP-SUM Bayes Filter
4.1 Updating the Prediction Belief
4.2 Recovering the Belief from the Prediction Belief
4.3 Computational Complexity
5 Results
5.1 Synthetic Task: Algorithm Evaluation and Comparison
5.2 Real Task: Propagating Uncertainty in Pushing
6 Discussion and Future Work
References
Optimal Motion Generation
Time-Optimal Motion of Spatial Dubins Systems
1 Introduction
2 Related Work
3 Model of Constant-Control Rigid Bodies
4 Necessary Conditions for Time-Optimal Trajectories
4.1 The Constraint Jacobian
4.2 Geometric Interpretation of Necessary Conditions
4.3 Geometric Relationship Between and Trajectory Structure
5 Finding Time-Optimal Trajectories
5.1 Finding Given Partial Trajectory Structure and Durations
5.2 Screw Actions
5.3 Fastest Trajectory for a Given
5.4 Complete Procedure
5.5 Approximation Theorems
5.6 Synthesis of Time-Optimal Control Sequences
6 Planning Algorithm Examples and Results
6.1 Trajectories with Many Switches
7 Conclusions
References
Robust Tracking with Model Mismatch for Fast and Safe Planning: An SOS Optimization Approach
1 Introduction
2 Preliminaries
2.1 Problem Formulation
2.2 Sum-of-Squares (SOS) Programming Background
3 SOS-Based Robust Tracking
3.1 Relative System
3.2 Optimization Problem
3.3 Reformulating the Constraints as SOS Certificates
3.4 Reformulating the Objective as SOS Certificates
3.5 SOS Formulation of Optimization Problem
4 Solving the Bilinear Optimization Problem
4.1 The K Sub-problem
4.2 The V Sub-problem
4.3 Solution Algorithm
5 Numerical Examples
5.1 Comparison with the HJ Method
5.2 High-Dimensional Example
6 Conclusions
References
Semi-infinite Programming for Trajectory Optimization with Nonconvex Obstacles
1 Introduction
2 Semi-infinite Programming with Collision Constraints
2.1 Semi-infinite Programming
2.2 Optimization with Instantiated Constraints
2.3 Collision-Free Constraint Formulation
2.4 Performance Notes
2.5 Most-Violating Parameter Calculation
2.6 Trajectory Collision Constraints
3 Experiments
3.1 Performance Characteristics
3.2 Trajectory Optimization
4 Conclusion
References
Signal Temporal Logic Meets Reachability: Connections and Applications
1 Introduction
2 Preliminaries
2.1 System Dynamics and Trajectories
2.2 Signal Temporal Logic
2.3 Time-Varying Reachability
2.4 Problem Formulation
3 STL Specifications in the HJI Context
3.1 STL Logical and Elementary Set Operations, and Functional Representations
3.2 ``Until'' and ``always'' as Reachability Operators
4 Controller Synthesis
4.1 Negation, Logical Disjunction, and ``always'': No Control Conflicts
4.2 Logical Conjunction and ``until'': Avoiding Control Conflicts
5 Practical Summary of Theoretical Results
5.1 List of Corresponding STL, Set, and Reachability Operators
5.2 Illustrative Example
5.3 Minimum Violation Interpretation
6 Simulations and Experiments
6.1 Hardware Setup
6.2 Highway Example
7 Conclusions and Future Work
References
Low Complexity Control Policy Synthesis for Embodied Computation in Synthetic Cells
1 Introduction
2 Related Work
3 Motivating Example: Synthetic Cells
4 Design Complexity and Task Embodiment
5 Control Modes Based on State
5.1 Switched Systems
5.2 Hybrid Optimal Control
5.3 Iterative Algorithm
5.4 Examples
6 Projecting Policies onto Discrete Sensors
7 Discussion
References
Tools for Perception, Kinematics and Dynamics
Parallax Bundle Adjustment on Manifold with Improved Global Initialization
1 Introduction
2 Parallax Bundle Adjustment on Manifold
2.1 Feature Parameterization
2.2 State Variable Retraction in Manifold
2.3 Error Function and Optimization Formulation
2.4 Theoretical Analysis on Convergence Properties
3 Global Initialization
3.1 Orientation and Feature Initialization
3.2 Position Initialization
3.3 Theoretical Analysis
4 Evaluation on PMBA Performance
4.1 Simulation
4.2 Large Dataset Test
4.3 Evaluation of PMBA Global Initialization
5 Conclusion
References
Practical Exponential Coordinates Using Implicit Dual Quaternions
1 Introduction
2 Related Work
3 Rotation and Transformation Matrix Maps
3.1 Rotation Matrix
3.2 Transformation Matrix
4 Ordinary, Dual, and Implicit Quaternion Maps
4.1 Ordinary Quaternions
4.2 Dual Quaternion
4.3 Quaternion-Translations as Implicit Dual Quaternions
5 Application to Kinematics
6 Discussion
7 Conclusion
References
A Performance Analysis of Parallel Differential Dynamic Programming on a GPU
1 Introduction
1.1 Related Work
2 DDP Background
3 Parallelizing DDP
3.1 Instruction-Level Parallelization
3.2 Algorithm-Level Parallelization
4 Implementation
5 Results
5.1 Quadrotor
5.2 Manipulator
5.3 Model-Predictive Control for the Manipulator
6 Conclusion and Future Work
References
Time Integrating Articulated Body Dynamics Using Position-Based Collocation Methods
1 Introduction
2 Related Work
2.1 Articulated Body Dynamics
2.2 Time Integration Schemes
2.3 Position-Based Dynamics (PBD)
3 Background: Lagrangian Articulated Body Dynamics
4 Position-Based Articulated Body Dynamics
4.1 High-Order Position-Based Collocation Method
5 Optimization Algorithm
5.1 Algorithm Complexity of High-Order Collocation Methods
5.2 GPU Parallelization
6 Results and Applications
6.1 Comparison
6.2 External Force Models and Applications in Controller Optimization
7 Conclusion, Limitations and Future Work
References
Efficient Computation of Higher-Order Variational Integrators in Robotic Simulation and Trajectory Optimization
1 Introduction
2 Preliminaries and Notation
2.1 Higher-Order Variational Integrators
2.2 The Lie Group Formulation of Rigid Body Motion
2.3 The Tree Representation of Mechanical Systems
3 The Linear-Time Higher-Order Variational Integrator
3.1 The DEL Equation Evaluation
3.2 Exact Newton Direction Computation
3.3 Extension to Constrained Mechanical Systems
4 The Linearization of Higher-Order Variational Integrators
5 Comparison with Existing Methods
5.1 Comparison with the Linear-Time Quasi-Newton Method
5.2 Comparison with Automatic Differentiation
5.3 Comparison with the Hermite-Simpson Direct Collocation Method
6 Implementation for Trajectory Optimization
6.1 Spring Flamingo
6.2 LittleDog
6.3 Atlas
7 Conclusion
References
Multi-Robot and Multi-Body Systems
Interlocking Block Assembly
1 Introduction
2 Limitations
3 Related Work
4 Interlocking Blocks and Constraint Graph
4.1 The Constraint Graph
4.2 Overview of the Layout Algorithm
5 Blocks and Squares
6 Segments
6.1 Structure Mirrors
7 Layers
7.1 Layer Key(s)
7.2 Segment Construction Order
7.3 Special Cases
8 Automatic Assembly and Parallel Construction
8.1 Parallel Construction
9 Results and Robotic Assembly
References
CADbots: Algorithmic Aspects of Manipulating Programmable Matter with Finite Automata
1 Introduction
1.1 Our Results
1.2 Related Work
2 Preliminaries
3 Basic Tools
3.1 Bounding Box Construction
3.2 Binary Counter
4 Counting Problems
4.1 Counting Tiles
4.2 Counting Corners
5 Transformations with Turing Machines
6 CAD Functions
6.1 Copying a Polyomino
6.2 Reflecting a Polyomino
6.3 Rotating a Polyomino
6.4 Scaling a Polyomino
7 Conclusion
References
Multi-agent Trajectory Prediction and Generation with Topological Invariants Enforced by Hamiltonian Dynamics
1 Introduction
2 Related Work
3 Foundations
3.1 Hamiltonian Motion for Multi-particle Trajectory Braiding
3.2 Topological Invariants of Particle Trajectories
3.3 Two-Particle Vortex Motion
3.4 Two-Agent Collision Avoidance as Vortex Motion
3.5 Multi-agent Trajectory Generation from Topological Specifications
3.6 TANP: Topologically Adaptive Navigation Planning
3.7 Complexity and Practical Considerations
4 Evaluation
4.1 Offline Performance
4.2 Comparison with Trajectory Optimization
4.3 Online Performance
5 Discussion and Future Work
References
Balancing Unpredictability and Coverage in Adversarial Patrolling Settings
1 Introduction
2 Related Work
3 Problem Definition
4 Background in Markov Chains
4.1 Relationships Between and P
5 An Unforecastable Patrolling Strategy
5.1 Optimizing Against an Observing Attacker
6 Experimental Evaluation
6.1 Comparing Against a Heuristic Strategy
6.2 Performance Against an Observer
7 Conclusions
References
Fast, High-Quality Dual-Arm Rearrangement in Synchronous, Monotone Tabletop Setups
1 Introduction
2 Related Work
3 Problem Setup and Notation
4 Baseline Approaches and Size of Search Space
5 Efficient Solution via Tour over Matching
6 Integration with Motion Planning
7 Bounding Costs Under Planar Disc Manipulator Model
8 Evaluation
9 Discussion
References
Optimality, Completeness, and Complexity in Planning
Motion Planning for Multiple Unit-Ball Robots in Rd
1 Introduction
1.1 Previous Work
1.2 Contribution
2 Algorithmic Framework
2.1 Preliminaries and Assumptions
2.2 Algorithm Overview
2.3 Retraction
2.4 Constructing a New Path
2.5 The Algorithm
3 Concrete Methods
3.1 Finding Revolving Areas
3.2 Finding Original Paths
3.3 Computing Intersections
4 General Analysis
5 The Case of Shortest Paths in R2
5.1 Construction of a Bad Input for Shortest Paths in R2
6 Finding Optimal Order of Paths Is NP-Hard
6.1 Problem Definition and Hardness Proof
6.2 Heuristic for Determining the Order
7 Experiments
7.1 Implementation Details
7.2 Experiments
7.3 Conclusions
References
Coordinating the Motion of Labeled Discs with Optimality Guarantees under Extreme Density
1 Introduction
2 Preliminaries
2.1 Labeled Disc Routing: Problem Statement
2.2 Workspace Discretization
3 Translating Continuous Problems to Discrete Problems with Minimal Penalty on Optimality
4 Constant-Factor Time-Optimal Multi-robot Routing on Triangular Grid
5 Fast Computation of Near-Optimal Solutions via Integer Linear Programming
5.1 Integer Linear Programming Model for Multi-robot Routing On Triangular Grids
5.2 Performance Evaluation
6 Conclusion and Future Work
References
An Experimental Analysis on the Necessary and Sufficient Conditions for the RRT* Applied to Dynamical Systems
1 Introduction
2 Problem Definition
3 Conditions for Asymptotic Convergence of the RRT*
4 Methods Overview for Using the RRT* for Nonholonomic Dynamical Systems
5 Description of Local Planners: The Case of Time-Optimal Planning for a DDR
5.1 Local Planner L+W+T+
5.2 Local Planner L+W*T+
5.3 Local Planner L+W-T+
5.4 Local Planner L+W-T-
5.5 Local Planner L-W-T-
6 Experimental Analysis of the Convergence: The Case of Time-Optimal Planning for a DDR
6.1 Experiment 1
6.2 Experiment 2
7 Discussion and Conclusions
References
Hardness of 3D Motion Planning Under Obstacle Uncertainty
1 Introduction
2 Background
2.1 Complexity in Motion Planning
2.2 Planning Under Uncertainty
3 Problem Formulation
3.1 Notation
3.2 Random Obstacle Model
3.3 Algorithmic Question
3.4 Graph Restriction
4 Basic Hardness Result
4.1 3SAT
4.2 Proof Outline
4.3 Proof
5 Hardness Result in R3
5.1 Proof
6 Conclusions and Future Work
References
The Hardness of Minimizing Design Cost Subject to Planning Problems
1 Introduction
2 Related Work
3 Definitions and Problem Formulation
3.1 Planning Problems and Plans
3.2 Design Costs
4 Hardness of Design Cost Minimization
4.1 The General Case
4.2 Special Cases that Are Also Hard
4.3 Hardness of Approximation
4.4 Fixed Parameter Hardness
5 Design Cost Minimization in Polynomial Time
5.1 Binary Design and Ordered Action Costs Are Efficiently Solvable
5.2 Counter Design Cost Is Fixed Parameter Tractable
6 Discussion
References
Human-Robot Interaction
Altruistic Autonomy: Beating Congestion on Shared Roads
1 Introduction
2 Model and Problem Statement
3 Main Results
4 Experiments
5 Discussion
References
Operation and Imitation Under Safety-Aware Shared Control
1 Introduction
2 Background and Related Work
3 Safety-Aware Shared Control
3.1 Safety-Aware Autonomous Policy Generation
3.2 Safety-Aware Dynamic Control Allocation
3.3 Safety-Aware Shared Control Imitation Learning
4 Empirical Evaluation
4.1 Experimental System
4.2 Implementation Details
4.3 Study Protocol
5 Experimental Results
5.1 Safety-Aware Shared Control Enables Successful Demonstration
5.2 Impact of Safety-Aware Shared Control on Trajectory Features
5.3 Safety-Aware Shared Control as a Training Mechanism
5.4 Safety-Aware Shared Control Improves Imitation Learning
6 Discussion and Conclusion
References
Guided Exploration of Human Intentions for Human-Robot Interaction
1 Introduction
2 Related Work
3 Intention POMDP-lite with Guided Exploration
3.1 Mathematical Formulation of Human-Robot Interaction
3.2 Intention-Driven Human Behavior Modeling
3.3 Intention POMDP-lite
3.4 Guided Exploration
4 Learning Human Behavior Policies and Guided Robot Exploration
4.1 Data Collection
4.2 Human Behavior Policy
4.3 Probability Distribution for Guided Exploration
5 Simulation Experiments
5.1 Driving Scenarios
5.2 Quantitative Results
6 Discussion
References
Counterexample-Guided Safety Contracts for Autonomous Driving
1 Introduction
2 Problem Statement
2.1 Stochastic Models of the Traffic System
2.2 Problem Formulation
3 Constructing Safety Contracts
3.1 Gradient-Based Probabilistic Falsification
3.2 Collision-Free Safety Conditions
3.3 Reachability with Contracts
3.4 Rules of the Road
4 Results
4.1 Leading/Trailing Car Scenarios
5 Conclusion
References
Author Index

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Algorithmic Foundations of Robotics XIII

Description

More details

Other editions

Additional editions

Content

System requirements