Algorithmic Foundations of Robotics XV: Proceedings of the Fifteenth Workshop on the Algorithmic Foundations of Robotics

Series Editor Foreword
Organization
Preface
Contents
Parametrized Motion Planning and Topological Complexity
	1 Introduction
	2 Parametrized Motion Planning Algorithms
	3 Multiple Robots and Obstacles in Euclidean Space
	4 Upper and Lower Bounds for TC[p:EB]
	5 Algorithm
		5.1 Subsets Aj,t
		5.2 Aggregation
		5.3 The Generic Case
		5.4 Sections and Fibrewise Deformations
		5.5 Sets A2n, t
		5.6 Swapping Deformations
		5.7 The Section s2n, t
		5.8 Desingularization
	6 Motion Planning Algorithm in Even Dimensions
	7 Parametrized Topological Complexity of Sphere Bundles and the Stiefel—Whitney Characteristic Classes
	8 Examples
	References
A New Application of Discrete Morse Theory to Optimizing Safe Motion Planning Paths
	1 Introduction
	2 Related Work
	3 Foundations
	4 Methodology
		4.1 Feasible Critical Points in Cspace
		4.2 Generating -Clearance Samples in the Cspace
	5 Experimental Setup
	6 Results
		6.1 Topology Map
		6.2 Comparison to RRT-Based Algorithms
		6.3 Comparison to PRM-Based Algorithms
		6.4 Comparison with Existing Work in a 2D Environment
	7 Discussion
	8 Conclusion
	References
Design Space Exploration for Sampling-Based Motion Planning Programs with Combinatory Logic Synthesis
	1 Introduction
	2 Related Work
		2.1 Type-Directed Synthesis
		2.2 Learning and Design Space Exploration
	3 Preliminaries
		3.1 Multi-objective Optimization Problem
		3.2 Black-Box Optimization
		3.3 Combinatory Logic Synthesis
	4 Architectural Overview
		4.1 A Repository for Sampling Based Motion Planning
		4.2 Encoding Domain Knowledge in Semantic Types
	5 Experiments
		5.1 3D Rigid Body Planning
		5.2 Motion Planning for Configurable Robotic Arms
	6 Discussion
	References
Large-Scale Heterogeneous Multi-robot Coverage via Domain Decomposition and Generative Allocation
	1 Introduction
	2 Domain Decomposition
	3 Generative Task Allocation
		3.1 Preliminaries
		3.2 Evolution-Guided GAN
	4 Local Trajectory Planning and Coverage Calculation
	5 Experiments
		5.1 Coverage Comparison
		5.2 Pareto Front Comparison
	6 Conclusion
	References
Efficient Motion Planning Under Obstacle Uncertainty with Local Dependencies
	1 Introduction
		1.1 Approximations in Planning with Environment Uncertainty
		1.2 Related Work
		1.3 Summary of Formal and Experimental Results
	2 Definitions
		2.1 Formal Problem Definition
		2.2 Formal Definition of Collision Horizon
	3 Algorithm
		3.1 Application to MCR
	4 Empirical Results
		4.1 Moving Boxes Domain
		4.2 Additional Experiments
	5 Conclusion and Future Work
	References
Distributed Spacing Control for Multiple, Buoyancy-Controlled Underwater Robots
	1 Introduction
	2 Preliminaries
		2.1 Graph Theory
		2.2 Potential Function
	3 Problem Formulation
	4 Technical Approach
		4.1 Construction of Potential Function
		4.2 Backstepping Controller Design
	5 Simulation Results
	6 Conclusion
	References
Decentralized Robot Swarm Clustering: Adding Resilience to Malicious Masquerade Attacks
	1 Introduction
	2 Related Work
	3 Notation and Problem Statements
		3.1 Attack and IDRS Model
		3.2 Formal Problem Statements
	4 Distributed Swarm DBSCAN, Attack, and IDRS
	5 Distributed Swarm k-Means: Algorithm, Attack, IDRS
	6 Experiments
		6.1 Silhouette Coefficient Performance Metric
		6.2 Experimental Process
	7 Discussion of Results
	8 Conclusion
	References
The Role of Heterogeneity in Autonomous Perimeter Defense Problems
	1 Introduction
	2 Problem Statement
		2.1 Perimeter Defense Against Point Attacks
		2.2 Different Settings
	3 Infinite Horizon Theoretical Results
		3.1 Dynamic Programming with Infinite Horizon
		3.2 Monotonicity-Based Computational Acceleration
	4 Unit Horizon Theoretical Results
		4.1 Policy and Reward
		4.2 Optimal Defender Policy
	5 Simulation Results
		5.1 Simulation Results
		5.2 Simulations for Unit Horizon
	6 Conclusion
	References
PiP-X: Funnel-Based Online Feedback Motion Planning/Replanning in Dynamic Environments
	1 Introduction
	2 Related Work
	3 Preliminaries
		3.1 Invariant Set Theory
		3.2 Verified Trajectory Libraries
		3.3 Discrete Graph-Based Replanning Using Incremental Search
	4 Problem Formulation
	5 Approach
		5.1 Graph Data Structure to Represent a Volumetric Funnel Network
		5.2 Online Motion Planning-Replanning Algorithm—PiP-X
		5.3 Precomputing Regions of Finite-Time Invariance
	6 Experimental Validation
	7 Results and Discussions
	8 Conclusions
	References
Sample-Efficient Safety Assurances Using Conformal Prediction
	1 Introduction
	2 Overview of Conformal Prediction
	3 Conformal Prediction Framework for Robotics Applications
		3.1 Problem Setup
		3.2 Analysis of the Trade-off Between the FNR and FPR
		3.3 Algorithm to Achieve Guaranteed Safety Assurances
		3.4 Comparing Conformal Prediction with PAC Learning
	4 Experiments: Driver Alert System
		4.1 Experimental Setup
		4.2 Results and Discussion
	5 Experiments: Robotic Grasping
	6 Conclusion
		6.1  Proofs
		6.2  Lower Bound on the False Positive Rate
		6.3 Additional Experimental Details: Driver Alert System
		6.4  Additional Experimental Details: Robotic Grasping Experiments
	References
Adaptive Discretization Using Voronoi Trees for Continuous-Action POMDPs
	1 Introduction
	2 Background and Related Work
	3 ADVT: Overview
	4 ADVT: Construction of the Belief Tree
		4.1 Action Selection Strategy
		4.2 Backup
	5 ADVT: Construction and Refinement of Voronoi Trees
		5.1 Refining the Partition
		5.2 Estimating the Voronoi Cell Diameters
		5.3 Sampling from the Voronoi Cells
	6 Experiments and Results
		6.1 Problem Scenarios
		6.2 Experimental Setup
		6.3 Results
	7 Conclusion
	References
Hierarchical Reinforcement Learning Under Mixed Observability
	1 Introduction
	2 Background
	3 Motion-Based MOMDPs
	4 Hierarchical Reinforcement Learning Under Mixed Observability
		4.1 Approach
		4.2 Bottom-Level Policy Learning
		4.3 Top-Level Policy Learning
		4.4 Optimality Analysis
	5 Related Work
	6 Experiments
		6.1 Domains
		6.2 Agents
		6.3 Learning Performance
		6.4 Comparing Full, Final, and Recurrent
		6.5 Robot Experiments for Two-Boxes
	7 Conclusion and Future Work
	References
Nondeterminism Subject to Output Commitment in Combinatorial Filters
	1 Introduction
	2 Basic Definitions
	3 Some Examples Leading to Our Key Definition
		3.1 An Interesting Filter and Two of Its Minimizers
		3.2 Processing Inputs Incrementally and String Single-Output Filters
		3.3 Classes of Minimizer
		3.4 Aside: Single- And Multi-output Vertices
		3.5 The Role of Output Simulation and Consistency Across Sequences
	4 Hardness of fm(dfdf), fm(dfsso), and fm(dfsmo)
		4.1 Complexity of fm(dfdf), fm(dfsso), and fm(dfsmo)
		4.2 Minimization Problems with a Unitary Alphabet
	5 Differences Between String Single-Output Minimization and General Tracing-Nondeterministic Minimization
	6 Summary and Conclusion
	References
Partial Satisfaction of Signal Temporal Logic Specifications for Coordination of Multi-robot Systems
	1 Introduction
	2 Preliminaries and Notation
		2.1 Signal Temporal Logic
	3 Problem Formulation
		3.1 Team Dynamics
		3.2 Partial Satisfaction Control Synthesis Problem
	4 Partial Satisfaction Encoding
		4.1 MILP Encoding of Satisfaction Fractions
		4.2 Objective Functions for Partial Satisfaction
		4.3 Partial Satisfaction Robustness LP
		4.4 Analysis
	5 Case Studies
		5.1 Continuous Space Multi-robot Planning
		5.2 Route Planning with Capability Temporal Logic (CaTL)
	6 Conclusions
	References
Information Theoretic Intent Disambiguation via Contextual Nudges for Assistive Shared Control
	1 Introduction
	2 Related Work
	3 Mathematical Formalism
		3.1 Modeling Limited Control-Interface Mediated Robot Teleoperation
		3.2 Recursive Bayesian Goal Inference
		3.3 Disambiguation Metric
	4 Shared Control via Contextual Nudges
	5 Experimental Design
		5.1 Experimental Setup
		5.2 Training Protocol
		5.3 Algorithm Evaluation
	6 Results
	7 Discussion
	8 Conclusion
	References
The Limits of Learning and Planning: Minimal Sufficient Information Transition Systems
	1 Introduction
	2 Mathematical Models of Robot-Environment Systems
	3 Sufficient Information Transition Systems
		3.1 Information Transition Systems
		3.2 History Information Spaces
		3.3 Sufficient State-Relabeling
		3.4 Derived Information Transition Systems
		3.5 Lattice of Information Transition Systems
	4 Solving Tasks Minimally
	5 Illustrative Examples
	6 Discussion
	References
Towards a Framework for Comparing the Complexity of Robotic Tasks
	1 Introduction
	2 Related Work
	3 Problem Formulation
	4 Task Reduction
		4.1 Background
		4.2 Task Reduction: Definition and Properties
	5 Examples of Reductions
		5.1 Navigation to a Goal with Map Rotations
		5.2 Grasping Objects with Differing Camera Viewpoints
	6 Relative Complexity
	7 Algorithmic Approach
	8 Examples
		8.1 Cartpole Balancing Task
		8.2 Mujoco 2D Walker at Varied Speeds
	9 Conclusion
	A  Proof of Properties
	B  Additional Experimental Details
	References
Exponential Convergence of Infeasibility Proofs for Kinematic Motion Planning
	1 Introduction
	2 Related Work
	3 Problem Definition
		3.1 Infeasibility Proofs
		3.2 Configuration Space Requirements
		3.3 Summary of Infeasibility Proof Algorithm
	4 Convergence Analysis
		4.1 Requirements on the Learning Method
		4.2 Preliminary Definitions
		4.3 Proof of Convergence
		4.4 Proof of Exponential Convergence
	5 Experiments
	6 Conclusion and Discussion
	A  Appendix: Comparing PRM and RRT-Connect
	References
Lane-Level Route Planning for Autonomous Vehicles
	1 Introduction
	2 Preliminaries
		2.1 The Lane Graph Representation
		2.2 A Stochastic Model for Lane Changes
		2.3 The Markov Decision Process
	3 Computing the Optimal Policy
		3.1 Monotonicity Conditions
		3.2 Dijkstra-Like Algorithm
		3.3 Potential Heuristics
	4 Experiments
	5 Discussion
	References
Finding and Optimizing Certified, Collision-Free Regions in Configuration Space for Robot Manipulators
	1 Introduction and Related Work
	2 Problem Formulation
	3 Background
	4 Technical Approach
		4.1 Rational Parametrization of the Forward Kinematics
		4.2 The SOS Certification Problem
		4.3 Growing Polytopic Regions in Tangent-Configuration Space
	5 Results
		5.1 3-DOF Flipper System
		5.2 7-DOF KUKA with Shelf
		5.3 12-DOF Bimanual Example
	6 Conclusion and Future Work
	A  Definition of Archimedean
	B  Practical Aspects
		B.1  Choosing the Reference Frame
		B.2  Basis Selection
		B.3  Parallelization
		B.4  Seeding the Algorithm
	C  Supplementary Algorithms
	References
Safe Output Feedback Motion Planning from Images via Learned Perception Modules and Contraction Theory
	1 Introduction
	2 Related Work
	3 Preliminaries and Problem Statement
		3.1 Problem Statement
		3.2 Control/Observer Contraction Metrics (CCMs/OCMs)
	4 Method
		4.1 Learning a Perception Module for Contraction-Based Estimation
		4.2 Bounding Tracking Error and State Estimation Error for Planning
		4.3 Optimizing CCMs and OCMs for Output Feedback
		4.4 Solving the OFMP
	5 Results
	6 Discussion and Conclusion
	References
Implicit Multiagent Coordination at Uncontrolled Intersections via Topological Braids
	1 Introduction
	2 Related Work
	3 Problem Statement
	4 Preliminaries
		4.1 Topological Braids
		4.2 Transforming Traffic Trajectories into Braids
	5 Decentralized Navigation as Braid Prediction
		5.1 Reasoning About Braids of Multiagent Interaction
		5.2 Decision Making
	6 Application
		6.1 Setup
		6.2 Models
		6.3 Experiment Design
		6.4 Results
	7 Discussion
		7.1 Limitations
	References
Active Uncertainty Reduction for Human-Robot Interaction: An Implicit Dual Control Approach
	1 Introduction
	2 Related Work
	3 Preliminaries
	4 Problem Statement
	5 Active Uncertainty Reduction for Human-Robot Interaction
	6 Simulation Results
		6.1 Objective and Awareness Uncertainty (Example 1)
		6.2 Behavioral and Cooperative Uncertainty (Example 2)
		6.3 Multi-Agent Case Study
	7 Discussion and Future Work
	References
The Correlated Arc Orienteering Problem
	1 Introduction
	2 Related Work
	3 CAOP: Problem Statement
	4 Exact and Heuristic Approaches for CAOP
		4.1 Mixed Integer Quadratic Program for CAOP
		4.2 A Greedy Constructive Algorithm
		4.3 ComputeRoute: Constructive Edge-Insertion Routing Heuristic
	5 Application Scenarios for CAOP
		5.1 Gas Leak Estimation
		5.2 Coverage of Road Networks
	6 Conclusion
	References
Sample-Efficient Safe Learning for Online Nonlinear Control with Control Barrier Functions
	1 Introduction
	2 Preliminaries
		2.1 Dynamical System and Stochastic Control
		2.2 Discrete-Time Control Barrier Functions for Gaussian Dynamical Systems
		2.3 Learning Objective
	3 Algorithm and Analysis
		3.1 Calibrated Model and Approximate Safety Guarantee
		3.2 Optimism-Based Safe Learning for Control
	4 Results
	5 Conclusion
	References
Morse Graphs: Topological Tools for Analyzing the Global Dynamics of Robot Controllers
	1 Introduction
	2 Problem Setup
	3 Proposed Framework and Method
	4 Results
	5 Conclusion
	References
Flock Navigation by Coordinated Shepherds via Reinforcement Learning
	1 Introduction
	2 Related Work
	3 Problem Formulation
	4 Method
	5 Experiments and Results
	6 Conclusion
	References
Automatic Cross-domain Task Plan Transfer by Caching Abstract Skills
	1 Introduction
		1.1 Background
		1.2 Motivation
		1.3 Contribution
		1.4 Related Work
	2 Problem Definition
	3 Scalable Skill Transfer Through an Abstract Domain
	4 Skill Abstraction and Caching
		4.1 Representing Transferable Skills as Traces of States
		4.2 Abstraction Keys
		4.3 Parametric Abstraction Keys
		4.4 Abstract Skill Caching
		4.5 Exemplary Abstraction Key: Attention
		4.6 Exemplary Abstraction Key: Symbol Stripping
	5 Abstract Skill Reconstruction and Transfer
		5.1 Abstract Skill Applicability
		5.2 Skill Feasibility
		5.3 Skill Transfer Through an Abstract Domain: Recap
	6 Conclusion
	A  Algorithms
	References
GOMP-ST: Grasp Optimized Motion Planning for Suction Transport
	1 Introduction
	2 Related Work
		2.1 Motion Planning and Optimization
		2.2 Constraint Learning in Optimization
		2.3 Suction Grasping
		2.4 Dynamic Manipulation
	3 Problem Statement
	4 Method
		4.1 Background: GOMP-FIT
		4.2 Learned Constraints in the SQP
		4.3 Self-supervised Data Collection and Training
		4.4 Analytic Model of Suction-cup Failure for GOMP-FIT Baseline
	5 Experiments
		5.1 Ablation Studies
		5.2 Results
	6 Conclusion
	References
Error-Bounded Approximation of Pareto Fronts in Robot Planning Problems
	1 Introduction
		1.1 Related Work
	2 Problem Statement
	3 Problem Analysis
	4 Algorithm
		4.1 Algorithm Description
		4.2 Algorithm Properties
	5 Simulation Results
		5.1 Experiment 1: Dubins Trajectories
		5.2 Experiment 2: Reward Learning
	6 Discussion and Future Work
	References
GLiDE: Generalizable Quadrupedal Locomotion in Diverse Environments with a Centroidal Model
	1 Introduction
	2 Related Work
	3 GLiDE: RL with Centroidal Model
	4 Results
		4.1 Learning Challenging Tasks with GLiDE
		4.2 Sim-to-Real Tests
	5 Evaluation
		5.1 Test Scenarios
		5.2 Evaluation Results
	6 Discussion and Future Work
	References
A Lower Bounding Framework for Motion Planning Amid Dynamic Obstacles in 2D
	1 Introduction
	2 Preliminaries
	3 A Lower Bounding Problem Formulation
		3.1 Bi-Level Discretization
		3.2 Reachable Time Intervals and Self-Loops
		3.3 Lower Bounding Problem Definition
	4 Lower Bounding A*
		4.1 LB-A* Overview
		4.2 Compute Earliest Reachable Time
	5 Analysis
		5.1 Lower Bounds
		5.2 Computational Complexity
	6 Discussion
		6.1 Edges Between Sub-Segments
		6.2 Adding Expansion Constraints
	7 Numerical Results
		7.1 Experiment 1: Simple Instance with Known C*
		7.2 Experiment 2: One Dynamic Obstacle
		7.3 Experiment 3: Dynamic and Static Obstacles
		7.4 With and Without the Expansion Constraint
		7.5 Computational Burden
	8 Conclusion
	References
Author Index