Algorithmic Foundations of Robotics IX: Selected Contributions of the Ninth International Workshop on the Algorithmic Foundations of Robotics

Cover......Page 1
Front Matter......Page 2
 Problem Description......Page 3
  Sensors and the Observation History......Page 4
  The Verification Problem......Page 5
  Single G-Folds on Unstacked Geometry......Page 6
  Model Linearization and Discretization......Page 7
  Experimental Setup......Page 10
  Exact Minima for Peptide Plane Orientations from Multiple φ -Defining RDCs and Multiple ψ-Defining RDCs......Page 11
  Introduction......Page 13
  Related Work......Page 14
  Distance Manifolds: Cable-Obstacle Interaction......Page 15
   Configuration Space......Page 16
  Sequences of G-Folds and Stacked Geometry......Page 8
 Validating a Single Agent\'s Story against an Observation History of a Single Agent......Page 9
 Validating a Single Agent\'s Story against an Observation History of Multiple Agents......Page 12
   Graph Representation of Configuration Space......Page 17
   Plan Generation: Backward Search......Page 18
   Algorithm Analysis......Page 19
   Implementation Details......Page 22
   Hardware Solution: Cable Retraction......Page 23
   Deadlock Prevention......Page 25
  Experiments......Page 26
   Experimental Results......Page 27
  Conclusion......Page 28
  Introduction......Page 31
  Algorithms......Page 33
   Path Set Generation......Page 34
   Path Classification......Page 35
   Implicit Path Safety Test......Page 36
  Foundations......Page 37
   Properties of Paths......Page 38
   Equivalence Relation......Page 39
   Resolution Completeness of Path Classifier......Page 43
  Results......Page 44
  References......Page 45
  Introduction......Page 48
   Basic Definitions......Page 50
   Trajectory Transformations......Page 52
   Optimising a Trajectory......Page 54
  Path Correction Algorithm without Obstacles......Page 55
  Path Correction Algorithm with Obstacles......Page 59
  References......Page 62
 Asynchronous Distributed Motion Planning with Safety Guarantees under Second-Order Dynamics......Page 64
  Introduction......Page 82
  Problem Definition......Page 84
  Algorithm......Page 86
  Analysis......Page 89
  Simulation Examples......Page 92
  Conclusions......Page 95
  References......Page 96
  Introduction......Page 99
   The Standard Model......Page 101
   Our Results......Page 102
  One on One Kabaddi......Page 103
   The Second Phase of the Attack......Page 105
   Completing the Analysis......Page 108
  Strong Defenders......Page 109
  Strong Defenders with Manhattan Moves......Page 110
   One on One Game with Speedier Defender......Page 111
   Speedier Attacker against Multiple Defenders......Page 112
  Discussion......Page 113
  Introduction......Page 115
   Carpenter\'s Rule Theorem and the CDR Algorithm......Page 116
   Slender Adornment......Page 118
   Modules......Page 119
   The Centralized Algorithm......Page 120
   The Decentralized Algorithm......Page 121
  Conclusion......Page 128
  References......Page 129
  Introduction......Page 131
  Related Work......Page 133
   Fast Locomotion......Page 136
   Stable Locomotion......Page 137
   Scalable Locomotion......Page 138
   Algorithm Outline: One Tunnel......Page 139
   Algorithm Outline: Connecting Adjacent Tunnels......Page 140
   Other Challenges Solved......Page 141
   Shape and Terrain Limitations......Page 142
  Simulation Results......Page 143
   Speed Comparisons......Page 144
  References......Page 146
  Introduction......Page 148
  Related Work......Page 149
   Assumptions and Notation......Page 151
   Adaptive Time-Stepping with Exponential Backoff......Page 152
   Completeness and Competitiveness......Page 154
   Completeness and Sensitivity Experiments......Page 155
   Assisted Teleoperation Experiments on a 6DOF Manipulator......Page 156
   Conservative Replanning Framework......Page 158
   A Contingency Replanning Algorithm......Page 159
   Experiments on a Pursuit-Evasion Example......Page 161
  Conclusion......Page 162
  References......Page 163
  Introduction......Page 165
  Problem Statement......Page 167
  The Bayes Tree......Page 169
  Incremental Inference......Page 171
  Incremental Reordering......Page 173
  Exact Incremental Inference with Fluid Relinearization......Page 174
  Experimental Results......Page 176
  References......Page 179
  Introduction......Page 182
   Preliminaries on POMDPs......Page 183
   Related Work......Page 185
   Policy Graphs......Page 186
   Algorithm......Page 191
   Navigation......Page 192
   Grasping......Page 194
   Discussion......Page 196
  Conclusion......Page 197
  Introduction......Page 199
  Related Work......Page 201
  Problem Definition......Page 202
   POMDP Modeling......Page 203
   QMDP Policy......Page 204
   Computing Value Functions for the Fully-Observable Problem......Page 206
   Expected Information Gain Scoring Strategy......Page 207
   Complexity and Convergence......Page 208
   Pursuit Scenario......Page 209
   Localization Scenario......Page 211
  Discussion: Exploration Strategies......Page 212
  References......Page 213
  Introduction......Page 216
   Real-Time Motion Planning......Page 218
   GPU Architectures......Page 219
   Collision Queries: Hierarchical Traversal......Page 220
  Parallel Collision Detection on GPUs......Page 221
   Parallel Collision-Packet Traversal......Page 222
   Parallel Collision Query with Workload Balancing......Page 224
   Analysis......Page 226
  Implementation and Results......Page 229
  Conclusion and Future Work......Page 231
  References......Page 232
  Introduction......Page 234
   Continuous Collision Detection......Page 236
   Notations and Assumptions......Page 237
   Local Planning in Sampling-Based Motion Planner......Page 238
   Conservative Advancement......Page 239
   Time of Violation Query for CCQ$_s$......Page 240
   Boolean Version of CCQ$_s$......Page 241
   Penetration Depth......Page 242
   Boolean Version of CCQ$_p$......Page 243
   Time of Violation Query for CCQ$_p$......Page 244
  Results and Discussion......Page 245
   Probabilistic Roadmap with CCQ......Page 246
   Rapidly-Exploring Random Tree with CCQ......Page 247
   Comparisons with Prior Approaches......Page 248
  Conclusions......Page 249
  References......Page 250
  Introduction......Page 253
   Background......Page 254
   Two Representations for the Contact Models......Page 256
   The Contact Models for Event-Driven and Time-Stepping Simulation......Page 258
   Time Stepping Method......Page 259
  Evaluating the Contact Models......Page 260
   Event-Driven Example: Internal Combustion Engine......Page 261
   Time-Stepping Example: Granular Matter......Page 262
  Modeling Joint Friction for Articulated Bodies Formulated in Reduced Coordinates......Page 264
   Solving the Joint Friction Model......Page 265
   Empirical Results......Page 266
  Conclusions......Page 267
  Introduction......Page 271
  Tangential Impulse......Page 273
   Impact Model......Page 274
   Contact Modes......Page 275
   Stick......Page 276
   Slip......Page 277
   Contact Mode Transitions......Page 278
   Impact Initialization......Page 279
   Ball......Page 281
   Pencil......Page 284
  Simultaneous Collisions with Compliance......Page 285
  Discussion......Page 286
  References......Page 287
  Introduction......Page 289
   Subtle Implementation Issues of Bi-RRT......Page 291
   The Promenade Motion-Planning Problem......Page 292
  Introducing the Automaton of Sampling-Diagrams......Page 293
   Relating ASDs to Bi-RRT – Swath-Realizing ASDs......Page 294
  Proving a Probabilistic Bound for the Promenade Problem......Page 295
   Aα Accepts Inputs That Induce ≤ μ-Quality Solutions......Page 297
   Probabilistic Analysis of Aα......Page 299
   Extensions to General lp and Arbitrarily Small μ......Page 300
  More Complex Settings......Page 301
  Conclusions......Page 303
  References......Page 304
  Introduction......Page 306
  Precompactness and Sampling Convergence......Page 308
  Problem Definition......Page 310
   Designing Metric Spaces on $U$ and $X$......Page 311
   Relating Controls to Trajectories......Page 312
   Topological Properties......Page 314
   Controls via Concatenation of Primitives......Page 315
   Planning Algorithm......Page 317
   Sufficient Conditions for Resolution Completeness......Page 318
  Conclusions......Page 321
  References......Page 322
  Introduction......Page 324
  Related Work on Finger Design......Page 325
   Geometric Reformulation of the Problem......Page 327
   General Solution Recipe......Page 329
   Case I: Rotation Center on the Contact Curve......Page 330
   Case II: Rotation Center at Finite Distance from Contact Curve......Page 331
   Family of Solutions......Page 332
   Scale Invariant Grasping......Page 334
   Pose Invariant Grasping......Page 335
   Pick-Up Tool......Page 336
   Anti Kickback Device for Table Saws......Page 337
   Jar Wrench......Page 338
  References......Page 339
  Introduction......Page 340
  Higher-Dimensional Continuation......Page 343
   Chart Selection: Focusing on the Path to the Goal......Page 346
   Algorithm......Page 347
  Experiments......Page 350
  Conclusions......Page 353
  References......Page 354
 Algorithms and Analytic Solutions Using Sparse Residual Dipolar Couplings for High-Resolution Automated Protein Backbone Structure Determination by NMR......Page 357
  Introduction......Page 358
  Background......Page 360
  The Protein Structure Determination Problem......Page 363
   Exact Solutions for Peptide Plane Orientations from One φ -Defining RDC and One ψ-Defining RDC......Page 364
   Exact Minima for Peptide Plane Orientations from Multiple φ -Defining RDCs and Multiple ψ-Defining RDCs......Page 367
  Alignment Tensors, Orientation of the First Peptide Plane, and Packing......Page 368
  Results......Page 369
  Conclusions......Page 372
  References......Page 373
  Introduction......Page 375
  Related Work......Page 377
  Needle Kinematics......Page 378
  LQG Control for Steerable Needles......Page 380
   Model Linearization and Discretization......Page 381
   Kalman Filter and LQR Controller......Page 383
   Obstacle Intersection Probability along a Path......Page 384
   Needle Controllability......Page 386
   Effect of Sensor Placement on Optimal Path......Page 387
   Optimizing the Sensor Placement......Page 388
  Conclusion and Future Work......Page 389
  References......Page 390
  Introduction......Page 392
   Workspace, Agents and Stories......Page 394
   Sensors and the Observation History......Page 395
   The Verification Problem......Page 396
  The Connectivity Graph and Sensing Induced Subgraphs......Page 397
  Validating a Single Agent\'s Story against an Observation History of a Single Agent......Page 400
  Validating a Single Agent\'s Story against an Observation History of Multiple Agents......Page 403
  Conclusion and Open Questions......Page 405
  References......Page 406
  Introduction......Page 409
  Related Work......Page 410
  Problem Description......Page 411
   Single G-Folds on Unstacked Geometry......Page 414
   Sequences of G-Folds and Stacked Geometry......Page 416
   Experimental Setup......Page 418
   Experimental Results......Page 421
  Conclusion and Future Work......Page 423
  References......Page 424
Back Matter......Page 425