
Algorithmic Foundations of Robotics XIII
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
This book gathers the outcomes of the thirteenth Workshop on the Algorithmic Foundations of Robotics (WAFR), the premier event for showcasing cutting-edge research on algorithmic robotics. The latest WAFR, held at Universidad Politécnica de Yucatán in Mérida, México on December 9-11, 2018, continued this tradition. This book contains fifty-four papers presented at WAFR, which highlight the latest research on fundamental algorithmic robotics (e.g., planning, learning, navigation, control, manipulation, optimality, completeness, and complexity) demonstrated through several applications involving multi-robot systems, perception, and contact manipulation. Addressing a diverse range of topics in papers prepared by expert contributors, the book reflects the state of the art and outlines future directions in the field of algorithmic robotics.
More details
Other editions
Additional 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
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.