Index

C0 function, 385

C∞ function, 385

C∞ manifold, see smooth manifold C∞ structure, see smooth structure Ck function, 385

GL(n), 145

K-step information-feedback plan, 568

L1 metric, see Manhattan metric L2 metric, see Euclidean metric L∞ metric, 187

Lp metric, 187–188

Lp norm, 188

SE(n), see special Euclidean group

C, see configuration space

Cobs, see obstacle region, in the C-space

Xobs, see obstacle region, in the state space

Xric, see obstacle region, in the state space

ǫ-goodness, 240

Ihist, see history information space

ndet, see nondeterministic information space

I

prob, see probabilistic information space

I

k-cell, 267

k-neighborhood, 221

(t,m,s)-nets, 208

(t,s)-sequences, 208

1-complex, 133

1. neighborhood, 221, 380
2. neighborhood, 221

3D triangles, 90–91

A∗ algorithm, 37, 223, 811

Abelian group, see commutative group acceleration vector, 408

acceleration-based control, 408–409

accelerometer, 601

accessibility (of a roadmap), 251 accessible system, 870, 909

accumulation point, 129

Ackerman function, 303, 304

action history, 400, 566

action sequence, 802

action trajectory, 400, 788 active localization problem, 642

active-passive decomposition, 343

actuators, 793

Adams methods, 815

adding integrators to a model, 742–744 adjoint transition equation, 877 adjoint variables, 779, 875

admissible configurations, 334

affine space, 170

affine-in-control system, see affine non- linear control system

AGVs, see automated guided vehicles airport terminal, 376

algebraic primitive, 87, 88, 130, 164–166 algebraic Riccati equation, 874 algebraic set, 87

algebraic variety, see variety alive states, 33, 55, 56, 427

Allen wrench, 701

Alpha Puzzle, 6

alphabet, 586

Amato, 6

ambient isotopy, 350

ambient space, 350

analytic function, 383

angular momentum, see moment of mo- mentum

angular velocity, 601, 727, 729, 756, 757,

760, 761

985

annihilator, 897

antipodal points, 138

approximate cell decomposition, 246 approximate cover, 413–415 approximate optimal motion planning,

359–360

approximation algorithm, 826–827 Ariadne’s Clew algorithm, 227 arrangement, 307

Asimo, 14

assembly planning, 321–322

asteroids game, 137

asymptotic convergence to a goal, 400 asymptotic solution plan, 400 asymptotic stability, 863–864

atan2, 99

atlas, see smooth structure automated farming, 354 automated guided vehicles, 325 automotive assembly, 6

autonomous differential equations, 387 average cost-per-stage model, 522, 524

average dispersion, 246

averaging methods, 921 axioms of rationality, 481–482

axis-aligned bounding box, 211

B-splines, 91

backprojection, 427, 503–505, 840–841,

852

in preimage planning, 696–700 backward action space, 40

backward P. Hall coordinates, 914, 916 backward reachable set, 801

backward search, 39–40, 219, 377, 696,

699, 703

with backprojections, 518–519 backward state transition equation, 40,

50, 53

backward system simulator, 816 backward value iteration, 45–48

for reinforcement learning, 534–535 for sequential games, 546–548

on a nondeterministic I-space, 637– 638

on a probabilistic I-space, 638–639 path-constrained, 852–853

running time, 46

under differential constraints, 839– 841

with average cost-per-stage, 527 with discounted cost, 525–526

with nature and continuous spaces, 551–552

with nondeterministic uncertainty, 508– 514

with probabilistic uncertainty, 510– 514

bad bracket, 910

Balkcom-Mason curves, 886–888

Balkcom-Mason drive, 887

Balkcom-Mason metric, 888

bang-bang approach, 853–855 Barraquand-Latombe nonholonomic plan-

ner, 828–832

base point (on a manifold), 895 base point of a path, 142

basis, 382

of open sets, 130

Basu-Pollack-Roy roadmap algorithm, 298 Battle of the Sexes, 471

Battleship game, 626–627

Bayes’ rule, 443, 458, 578, 653

Bayesian classifier, 456–458

naive, 457

behavioral strategies, 622 behaviors, see motion primitives best-first search, 38–39

bidirectional search, 40–41, 71, 227, 367,

638, 801, 819, 820, 827, 831, 835

balanced, 235–236

for sampling-based planning, 220 bijective sensor, 562

bilinear programming, 473

binding constraints, 63

bitangent line, 262

bitangent ray, 675

bitmap, 91–92

black-box simulators, 815–816

Blum and Furst, 64

Blum and Kozen, 660, 662

body density, 753

body frame, 94, 176, 178, 352, 366, 754,

758–760

bond angle, 111

bond length, 111

Borel sets, 192

boundary grid point, 221 boundary of a set, 129 boundary point, 129

boundary representation, 81

boundary sensors, 601–602

bounded set, 132

bounded-acceleration model, 409

bounded-velocity model, 409

Boustrophedon decomposition, 354–357

Brachistochrone curve, 762

bracket, 904

breadth-first search, 35

bridge-test sampling, 243–244 broad-phase collision detection, 210 Brockett, 741, 917, 919

Brockett’s condition, 864

Brockett’s system, see nonholonomic in- tegrator

bug algorithms, 667–673

bug trap, 219

Bug1 strategy, 668–669

Bug2 strategy, 669–670

BVP, see two-point boundary value prob- lem

C-space, see configuration space caffeine, 17

calculus of variations, 440, 762–769, 922

card-counting strategies, 630

Carnot-Caratheodory metric, 811

Cartesian product, 135

carton folding, 347–350

causal links, 63

CBHD formula, 913

cell decomposition, 251, 264–280, 650,

690

under differential constraints, 828 center of mass, 753

Central Limit Theorem, 199 chain of integrators, 738–739 chained-form system, 906, 920 change of coordinates, 391–393

chart, see coordinate neighborhood chasing a gap, 677

Chazelle, 250

Chen-Fliess series, 913–914

Chen-Fliess-Sussman equation, 914–916

chi-square test, 200

Chow-Rashevskii theorem, 908

Christoffel symbol, 770, 771

Church-Turing thesis, 19

classification rule, 456

classifier, 455–458

cleared region, 688

closed kinematic chains, 118, 167–180 motion planning for, 337–347

closed set, 128

closed system (in mechanics), 746–747 closed-loop

control law, 793

plan, 370

see also feedback plan closure of a set, 129, 195

Campbell-Baker-Hausdorff-Dynkin formulcal,osure space, 339

913

candidate Lyapunov function, 866 Candorcet paradox, 482

Canny, 293

codistribution, 897

coherent models, 212

Collins decomposition, see cylindrical al- gebraic decomposition

Canny’s roadmap algorithm, 293–298, 307,collision detection, 209–217

315, 324, 339

car pulling trailers, 13, 730–731 Caratheodory, solution sense of, 387

broad-phase, 210

checking a path segment, 214–217 hierarchical methods, 210–212

incremental methods, 212–214

narrow-phase, 210

two-phase, 210

collision pairs, 156

collision-detection, 812–813

collocation, 857

combinatorial motion planning, 249–307 cell decompositions, 264–280

introductory concepts, 249–251

polygonal case, 251–264

see also Canny’s roadmap algorithm

see also cylindrical algebraic decom- position

combinatorial roadmaps, 237

commutative group, 142, 898

commutative ring, 170

commutator, 898

commutator motion, 897–900, 911

compass, 600, 647

conditional plan, see feedback plan conditional probability, 443

configuration space, 127–180

obstacle, see obstacle region, C-space of 2D rigid bodies, 145–148

of 3D rigid bodies, 148–154 of chains of bodies, 154–155 of trees of bodies, 155

velocity constraints on, 716–735 conformations, 110, 351

connected space, 139

connectivity-preserving roadmap, 251 connector in a roadmap, 241 conservative approximations, 593–595

conservative system, 766 constant vector field, 384 constant-sum game, 492

contaminated region, 688 continuous Dijkstra paradigm, 357 continuous function, 131

compatible coordinate neighborhoods, 393continuous-steering car, 743–744

competitive ratio, 602, 672–673

complementary pair, 59 complete exclusion axiom, 70

completely integrable, 734, 893–894 completeness

overview, 185–186

see also probabilistic completeness

see also resolution completeness complex, 265–268

complexity class, 299

complexity of motion planning, 298–307 lower bounds, 298–302

upper bounds, 304–307

compliant motions, 692–693, 697

composition of funnels, 413–419, 702, 865

compressed mode, 330

computational algebraic geometry, 280– 298

Conchoid of Nicomedes, 277, 308 conditional Bayes’ risk, 453 conditional Bayes’ rule, 443 conditional expectation, 444

conditional independence, 443

contractible space, 144

control system, 715, 793

control-affine system, 741, 890–892

controllability matrix, 868 controllability of a system, 867–870

linear case, 868

small-time local, see small-time lo- cal controllability

controlled Markov process, 498 convex hull, 211, 388

convex polygon, 82–84

convex set, 82

convolution, 158

cooperative game theory, 490 coordinate neighborhood, 391

coordinates, 391

coordination space, 323

Coriolis matrix, 770

cost functional, 44, 359, 363, 501, 523,

625, 839

approximating, 424

quadratic, 874

cost-based learning, see reinforcement learn-

ing

cost-to-come, 36, 48–50, 799

cost-to-come iteration, see forward value iteration

cost-to-go, 37, 45–46, 361, 373, 375–377,

379, 380, 402, 404–407, 413, 420,

423–429, 551, 811, 835, 836, 839,

840, 852, 853

see also stationary cost-to-go func- tion

cost-to-go iteration, see backward value iteration

Coulomb friction, 693

counting measure, 193

covariance matrix, 596 cover of a set, 413

approximate, 414

coverage planning, 354–357

decoupled planning, 320, 841–855

decoupling vector fields, 849, 921

deformation retract, 260 degrees of freedom, 95

delayed-observation sensor, 564

Denavit-Hartenberg parameters, 103–106,

110, 149, 154, 167, 179

dense sequence, 195, 798

dense set, 195

dependent events, 443

depth-first search, 36

depth-mapping sensors, 603–605 derivation (on a manifold), 396

derived information space, 571–581, 592–

598

for continuous time, 597–598 derived information transition equation,

573

Coxeter-Freudenthal-Kuhn triangulation, determining the environment, 656–660

422

critical curves, 276

critical gap events, 674–675

critical point of a function, 295, 410 cube complex, 325–327

cubical partition, 828

CW-complex, 265

cycloid function, 762

cylinder over a cell, 270, 276, 290 cylindrical algebraic decomposition, 286–

293, 315, 324

for motion planning, 292–293 cylindrical decomposition, 269–270

cylindrical joint, 105

D∗ algorithm, see Stentz’s algorithm D’Alembert, 776

Davenport-Schinzel sequence, 302–304

Davis-Putnam procedure, 69

dead states, 33, 34, 37, 427

decision maker, 4, 437

decision problem, 283

decision theory, 437

decision vertex (in a game tree), 536 decision-theoretic learning, see reinforce-

ment learning

deterministic finite automaton, 31, 585

language, 31

deterministic plan, 538, 545, 621

DFA, see deterministic finite automaton DH parameters, see Denavit-Hartenberg

parameters Dial’s algorithm, 380

diameter function, 702

dielectric constant, 352

diffeomorphic spaces, 385

diffeomorphism, 385

differentiable manifold, see smooth man- ifold

differentiable structure, see smooth struc- ture

differential constraints, see differential models

differential drive, 908

Balkcom-Mason, see Balkcom-Mason drive

model, 726–729

second-order, 744

showing it is nonholonomic, 902 differential game, 782–783

against nature, 780

pursuit-evasion, 782

differential inclusion, 388, 780

differential models, 715–783

conversion from implicit to paramet- ric, 720–722

implicit representation, 716–718

parametric representation, 718–720

differential rotations, 755–756 differentially flat systems, 921 digital actor, 12

Dijkstra’s algorithm, 27, 36–37, 55–57,

377, 378, 380, 403, 404, 407, 426,

428, 552, 663, 666, 823, 840, 852

dominated plan, 364

Donald, 627, 697

double integrator, 737–738, 744, 747, 755,

790, 792, 796

lattice, 820–828

optimal planning for, 877–878 doubly connected edge list, 86, 252, 253,

258

drift, 739, 741, 793, 891

driftless, 741, 793

driftless system, 739, 891

controllability, 908–909

drug design, 15, 350–353

extension of to continuous spaces, 426–Dubins car, 725, 782, 794, 796, 800, 803,

429

with nondeterministic uncertainty, 519– 521

with probabilistic uncertainty, 521 dimension

806, 811, 817, 828, 829, 831, 832,

835, 838, 842, 844, 845, 848

plan-and-transform approach, 843–

844

reachability tree of, 803–804

of a manifold, 134

of a vector space, 383 directed roadmap, 315

Dirichlet boundary condition, 412 disconnection proof, 246

discount factor, 523

discounted cost model, 522–524 discrepancy, 205–209, 811–812

range space, 206

relation to dispersion, 207 discrete feasible planning, 29 discrete-time model, 801–808 discretization of , 221 dispersion, 201–205, 420, 811–812

C

relation to discrepancy, 207 distance between sets, 209–210 distance function, 209

distribution (of vector fields), 894–897 regular, 895

singular, 895–896

disturbed odd/even sensor, 564 disturbed sign sensor, 564

DM, see decision maker domain of attraction, 864–865 dominated action, 440

Dubins curves, 880–883

Dubins metric, 883

dynamic constraints, 891

dynamic game, see differential game dynamic programming, 27

applied to steering, 922 continuous-time, 870–879 see also Dijkstra’s algorithm

see also Hamilton-Jacobi-Bellman equa- tion

see also value iteration dynamics

of a particle, 747–752

of a rigid body, 753–762

of a set of particles, 752–753

of a two-link manipulator, 771–773 of chains of bodies, 769–773

of constrained bodies, 774–777 with nonconservative forces, 777

efficient algorithm, 299, 302, 304

elongated mode, 330

EM algorithm, 682–684 embedding of a manifold, 134 energy function, 347, 350, 352

equilibrium point of a vector field, 862

Erdmann, 696, 699

error detection and recovery (EDR), 697 Euclidean metric, 187

Euclidean motion model, 361–362 Euclidean norm, 188

Euclidean shortest paths, 357–358 Euler angles, 122

Euler approximation, 424

Euler integration, see numerical integra- tion, Euler

Euler-Lagrange equation, 765–770, 879,

891, 918, 922

with conservative forces, 777 event space, 442

exact motion planning, see combinato- rial motion planning

exit face, 403

exotic R4, 393

expansive-space planner, 227–228

expectation of a random variable, 444 expected-case analysis, 449, 508, 570 exploration vs. exploitation, 530 exponential map, 912–913 exponentially stable system, 864 EXPTIME, 299

extended Kalman filter, 617, 655

extended system, 910

exterior point, 129

extremal function, 764

falling particle, 767–768 fast Fourier transforms, 425 Faure sequence, 208 feasible planning

discrete, 29

with feedback, 373–374

feasible space (for closure constraints), 339

feature space, 456

feature vector, 456, 457

feedback control law, see feedback plan feedback motion planning

complete, optimal, 404–407 complete, some dynamics, 407–412 definitions, 398–402

motivation, 369–371

sampling-based, 412–429

under differential constraints, 837– 841

feedback plan, 372–373, 505–508

cost of, 507–508

graph representation of, 507 information feedback, 568–569 over a cover, 415–416

sensor feedback, 581 feedback planning

continuous, see feedback motion plan- ning

discrete, 371–381

feedback policy, see feedback plan feedback stabilization, 862

fiber over a base, 895 fictitious action variable, 911 field, 168–169

algebraically closed, 287

Filipov, solution sense of, 388, 398

fine motion planning, see manipulation planning

finite state machine, 31 firetruck, 731

first-order controllable systems, 919–920 first-order theory of the reals, 283

fixed point of a vector field, 862 fixed-path coordination, 323–325

fixed-roadmap coordination, 325–327

flashlight example, 59–61 Boolean expression for, 70 planning graph of, 67

flashlight sensor, 691

flat cylinder, 136

flat outputs, 921

flat torus, 137

flexible materials, 121 flying an airplane, 732–733 folding problems, 347–354

foliation, 799, 893

force, 747, 748, 751–755, 760, 761, 766,

767

resultant, 748, 752

force sensor, 601

formal Lie algebra, 912–913 forward projection, 501, 799

differential, 781

nondeterministic, 501–502

probabilistic, 502–503 under a fixed plan, 506

forward search, 33–39

A∗ algorithm, 37–38

best first, 38–39

breadth-first, 35

depth-first, 36

Dijkstra’s algorithm, 36–37

general, discrete, 33–35

iterative deepening, 39 forward value iteration, 48–50 four-bar mechanism, 175

frame axiom, 70

Fraunhofer Chalmers Centre, 8 Frazzoli, 809

free space, 156

free variables, 282

frequentist, 483–484

frequentist risk, 484

friction cone, 693

Frobenius theorem, 901–902

frontier set, 427, 520, 840 fully actuated system, 793 function space, 383, 590, 763

functional, 763

shortest-path, 764

fundamental group, 142–144

higher order, 144

of a simply connected space, 142 of RP2, 143–144

of S1, 142–143

of Tn, 143

Fundamental Lemma of the Calculus of

Variations, 765

Gabriely and Rimon, 355 gain constant, 409

game

alternating-play model, 538, 621

extensive form, 536

ladder-nested, 623

normal form, 536

open-loop model, 539, 621 sequential, see sequential game stage-by-stage model, 538, 621 unusual information model, 621 see also game theory

game against nature, 446–459 sequential, 496–508, 551–556

game graph, 544

game theory, 437, 459–476, 489–490, 536–

551, 619–627

information spaces in, 619–627 nonzero-sum, see nonzero-sum game sequential, see sequential game

zero-sum, see zero-sum game game tree, 536–544

information space over, 619–623 gap navigation tree, 673–679

gap sensor, 604

gap theorems, 287

garage configuration, 325

Gaussian sampling, 243 Geiger counter sensor, 602 general linear group, 145 general position, 255, 675

generalized coordinates, 767

generalized cylinder, 92 generalized damper model, 693 generalized forces, 768, 769, 776

generalized momentum, 779

generalized Voronoi diagram, see maximum- clearance roadmap

generator of a lattice, 204 geodesics, 766, 810

geometric modeling, 81–92

Gilbert-Johnson-Keerthi algorithm, 244

gingerbread face, 87, 284, 291 globally asymptotically stable, 865 globally positive definite, 866 globally randomized plan, 622 GNT, see gap navigation tree

goal recognizability, 582, 696

goal sensor, 667

Goldberg and Mason, 701 golden ratio, 209

Goursat normal form, 920 Gru¨bler’s formula, 180

gradient descent, 375, 401, 410 graph search

on an information space, 638 grasped configurations, 334

gray-scale map, 92, 665

great circle, 190

grid, 318

2D planning on, 29 feedback plan on, 374 infinite sequence, 204–205

localization on, see localization, dis- crete

multi-resolution, 205

navigation function on, 376–381 neighborhoods, 221

partial, 205

resolution issues, 223–224 set of environments, 655–662 standard, see standard grid Sukharev, see Sukharev grid see also lattice

grid point, 221

grid resolution, 201

group, 141

see also fundamental group

see also matrix groups group axioms, 141

group of n-dimensional rotation matri- ces, 146

guaranteed reachable, 512 guard in a roadmap, 241 gyroscope, 601

Haar measure, 193–195 hairy ball theorem, 400 half-edge, 86, 253

half-plane, 83

half-space, 87

Halton sequence, 207–208

Hamilton’s equations, 779, 879, 891, 922

Hamilton’s principle of least action, 766– 768

Hamilton-Jacobi-Bellman equation, 515,

870–873

Hamilton-Jacobi-Isaacs equation, 873

Hamiltonian function, 778, 779, 875 Hamiltonian mechanics, see mechanics,

Hamiltonian Hammersley point set, 207–208 harmonic potential function, 412 Hausdorff axiom, 131

Hausdorff space, 131

Heisenberg system, see nonholonomic in- tegrator

helicopter flight, 809

Hessian, 410

hide and seek, 11 hide-and-seek

see also pursuit-evasion game hierarchical inclusion of a plan, 23, 693 hierarchical planning, 23, 336

higher order controllability, 920 Hilbert space, 383

hill function, 866

history, 566

history information space, 565–567, 591–

592

at stage k, 567 at time t, 591

history information state, 566

history-based sensor mapping, 590, 591

hitch length, 730

holonomic, 735, 893

homeomorphic spaces, 132

homeomorphism, 132–134, 385, 391

homicidal chauffeur, 782–783

homing sensor, 602

homogeneous transformation matrix, 96, 97, 100–103, 105–108, 110, 121,

124, 145, 165–167

homology, 144

homotopic paths, 140

homotopy group, see fundamental group humanoid, 13, 14, 114

hybrid state space, 328 hybrid system, 327–332, 388

motion planning, 327

with nature, 552–556

I-map, see information mapping I-space, see information space

I-state, see information state ibuprofen, 17

ideal distance function, 811 identification of points, 136 identity sensor, 562, 598 implicit function theorem, 722

implicit velocity constraints, 718 improper prior, 485

incomparable actions, 440

incremental distance computation, 212 incremental sampling and searching

adapting search algorithms, 220–224 general framework, 217–220

under differential constraints, 820– 837

independent events, 443

independent-joint motion model, 361 inertia matrix, 756–759, 766

inertia operator, see inertia matrix inertia tensor, see inertia matrix inertial coordinate frame, 746–747, 754,

755, 762, 767

infimum, 439

infinite reflection (in a game), 489 infinite-horizon problem, 522–527

inflection ray, 674

information mapping, 571–574

sufficient, 573–574

information space, 559–627

continuous examples, 598–614

continuous time, 591–592 conversion to a state space, 570–571,

634–637

discrete examples, 581–589 for game theory, 619–627

in continuous state spaces, 589–614 limited memory, 580–581

sensor feedback, 580–581

see also history information space

see also nondeterministic information space

see also probabilistic information space

information state, 560

information transition equation, 570–571 derived, 573–574

information transition function, 570 information-conservative property, 688

information-feedback plan, 568

initial condition space, 566–567, 590

input string, 585

integrable system, 734

integral curve, 387–388

integral manifold, 893

integration, see numerical integration interior of a set, 129

interior point, 129

interpolation neighbors, 420 interpolation region (for value iteration),

422, 551

interval homeomorphisms, 132

intractable problem, 299 inverse Ackerman function, 304 inverse control problem, 816

inverse kinematics problem, 120 involutive distribution, 901

Isaacs, 782

isomorphic graphs, 133

isomorphic groups, 149

isomorphism, 132

iterative deepening, 39

Jacobi identity, 904, 907, 920

Jacobian, 294

jerk (third time derivative), 738, 853

joint encoder, 601 junction of links, 114

Kagami, 13

Kalman filter, 615–617 Kalman rank condition, 868 Kd-tree, 233–234, 417, 831

Khalil-Kleinfinger parameterization, 115

Khatib, 401

kidnapped-robot problem, 640

kinematic chain, 100

kinematic constraints, 791, 891

kinematic singularities, 346

kinematically controllable, 921 kinematics for wheeled systems, 722–731 Kineo CAM, 7, 16

kinetic energy, 752, 760, 766–769, 772,

776

kinodynamic planning, 792, 820–828

Klein bottle, 138

knot, 350

knot simplification, 350

knot vector, 91

Koditschek, 375, 410

Kolmogorov complexity, 61, 301

Kuffner, 6, 219

Kuhn, 622, 627

Kutzbach criterion, 180

L-shaped corridor example, 582–585 label-correcting algorithms, 56–57 ladder robot, see line-segment robot Lafferriere and Sussmann, 910 Lagrange multiplier, 774

Lagrangian function, 767, 769, 772, 776,

779

layered plan, 68

learning phase, 529

leaves of a foliation, 799, 893

Lebesgue integral, 193

Lebesgue measure, 193

left translation, 905

left-invariant vector field, 905 left-turn predicate, 263

Legendre transformation, 778

Legendre-Clebsch condition, 879

Leibniz rule, 396

Lennard-Jones radii, 352

Lens spaces, 138

level-set method, 430

LG, see linear Gaussian system Lie, 892

Lie algebra, 904–906

cross product example, 904–905

of the system distribution, 905–906 on Lie groups, 905

see also Philip Hall basis Lie algebra rank condition, 908 Lie bracket, 897–901, 904

Taylor series approximation of, 899– 900

Lie derivative, 866

Lie group, 145, 905

Lagrangian mechanics, see mechanics, La- ligand, 350

grangian, 127 landmark region detector, 602 landmark sensors, 602–603

language, 31, 588

LARC, see Lie algebra rank condition latitude in a grid, 661

Latombe, 127

lattice, 204, 208

limit curve, 853

limit cycle, 865

limit point of a set, 129 Lin-Canny, 245

line-segment robot, 273–280

line-sweep principle, see plane-sweep prin- ciple

linear combination, 382

for unconstrained mechanical systems,linear complementarity problem, 473

825–826

from double integrator, see double- integrator lattice

grid, see grid Laumond, 16, 791

lawn mowing, 354

layered graph, 65

linear differential game, 782

linear interpolation, 420

linear momentum, 751

linear programming, 440, 467, 855 linear sensing models, 598–600 linear space, 382

linear system, 739–741

observability, 740

time-varying, 741

linear transformations, 120

linear-Gaussian system, 615, 616, 655

linear-quadratic problems, 874–875

lost-cow problem, 672, 707

low-discrepancy sampling, 205–209

low-dispersion sampling, 201–205

lower envelope, 302–304, 467

lower pairs, 105

linear-quadratic-Gaussian (LQG) system, lower value of a game, 461, 540, 546

617, 875

link, 100

linkage, 100

linkage graph, 177

Lipschitz condition, 216, 387–388, 806,

819, 831, 840, 856

Lipschitz constant, 216, 388

LMT framework, see preimage planning, 692

local operator, 375, 377, 378, 401, 403,

410, 514, 839

continuous space, 401

local planning method, 217–220, 226–

228, 231, 238, 240, 241, 327, 855,

862, 869, 880, 883, 886, 888, 908,

910, 921

in plan-and-transform, 843, 845 under differential constraints, 816–

818, 833, 834, 836

local visibility sensor, 667 localization, 640–684

active, 640, 644–646

combinatorial, 647–651

discrete, 640–647

passive, 640, 642–644

probabilistic, 651–655

symmetries, 643–644 locally positive definite, 866 locally randomized plan, 622 Logabex LX4 robot, 348 logic-based planning, 57–71

as satisfiability, 69–71 converting to state space, 61–62 in plan space, 63–64

operator, 58

via a planning graph, 64–69 logical predicate, see predicate loop path, 142

Lozano-P´erez, 127

Lozano-P´erez, Mason, and Taylor, 692 LPM, see local planning method lunar lander, 748–750

Lyapunov function, 413, 865–867

in planning, 867

Lyapunov stability, 862–863

uniform, 863 Lynch and Mason, 732

M¨obius band, 136, 138, 144, 183

Mahalanobis metric, 811

maneuver, 809

maneuver automaton, 809

Manhattan metric, 187

Manhattan motion model, 360–361 manifold, 134–139

embedding, 134

higher dimensional, 138–139

one-dimensional, 135–136

two-dimensional, 136–138

with boundary, 134

see also smooth manifold manipulation graph, 335–336

manipulation planning, 332–337 nonprehensile, see nonprehensile ma-

nipulation

under uncertainty, 691–704

manipulator, 107, 118, 122, 332–339, 348,

771–773, 846, 851

map building, 655–684

marginalization, 443–444, 502, 503, 578,

652

Markov chain, 498

Markov decision process, 498 Markov game, 550

Markov process, 498, 499

mass matrix, 766

matching pennies, 446

Matlab, 856

matrix game, 460

matrix groups, 145–148

matrix subgroup, 146

maximal ball, 244

maximum-clearance navigation function, 379–380

maximum-clearance roadmap, 260–261

maze searching, 660–662

MDP, see Markov decision process Mealy/Moore machines, 31

means-end analysis, 71

measurable function, 193

measurable sets, 192

measure axioms, 192

measure space, 186

measure theory, 191–195, 811

see also Haar measure measure zero, 193

mechanics, 745–780

Hamiltonian, 778–780

Lagrangian, 762–777

Newton-Euler, 745–762

see also dynamics medial-axis sampling, 244

Mersenne twister, 200

metric space, 186–188 Cartesian products of, 188 definition, 187

for motion planning, 188–191 from SE(2), 189

from SE(3), 191

from SO(2), 188–189

from SO(3), 189–190

from Tn, 190–191

nonpositively curved, 857

Riemannian manifold, 810–811 robot displacement metric, 190 subspaces of, 188

metric tensor, 810 metrics, see metric space metrizable, 187

mine sweeping, 354

minimalism, 700

minimax, 448

minimum turning radius, 725 Minkowski difference, 158, 252, 305

Minkowski sum, 158

mixed Nash equilibrium, see Nash equi- librium, randomized

mixed strategy, see randomized strategy mod sensor, 562

mode space, 327

mode transition function, 328 mode-dependent dynamics, 327 moment of a density, 597 moment of force, see torque, 753 moment of inertia, 758

moment of momentum, 751–753, 755,

761

moment-based approximations, 595–597

momentum, 751

monomial, 169

monotone polygon, 269

Monte-Carlo localization, see localiza- tion, probabilistic

morphing a path, 140 Morse function, 411

Morse theory, 411

motion capture, 858

motion command, 694–695

motion library, see motion primitives motion planning, 793

motion primitive, 808–810, 836

multi-body dynamics, see dynamics, of multiple bodies

multi-chained-form systems, 920

multi-level approach, 845

multi-linear interpolation, 421

multi-resolution grid, 204

multiobjective optimization, 440–441 multiple observations, 454

multiple query, 186, 237

multiple shooting, 857

multiple-robot motion planning, 318–327 multiple-robot optimality, 362–364

multiply connected, 141

Murphy’s Law, 448

Murray and Sastry, 917 mutex condition, 66–67

mutex relation, 66

NAG Fortran Library, 856 naive Bayes, 454

narrow-phase collision detection, 210 NASA/Lockheed Martin X-33, 795 Nash equilibrium, 468–475, 490, 619, 626

admissible, 471

in a sequential game, 548–549 nonuniqueness, 470–472

randomized, 472–474, 476, 622

nature, 437, 447

nature action space, 447 nature observation action, 453

nature sensing action, 563, 564, 590, 598–

599, 609–612

nature sensing actions, 561 navigation function, 35, 52, 375–381

continuous space, 402

in the sense of Rimon-Koditschek, 410–412

stochastic, 553

navigation problem, 657, 660

negative literal, 58

neighborhood function, 241 neighborhood of a cover, 414 Neumann boundary condition, 412

neuro-dynamic programming, see rein- forcement learning

Newton’s laws, 747–752, 755, 757, 766,

768

Newton-Euler mechanics, see mechan- ics, Newton-Euler

next-best-view problem, 680 NF2 (a navigation function), 379

NFA, see nondeterministic finite automa- ton

nicotine, 17

nilpotent, 910

nilpotent system, 908

nilpotentizable, 910

Nilsson, 72

Nixederreiter-Xing sequence, 208

nonconservative forces, 777 nonconvex

polygon, 84–85, 90

polyhedron, 90

set, 82

noncooperative game, 438

noncritical regions, 277 nondeterministic finite automaton, 585–

589

nondeterministic information space, 574– 577

approximations, 593–595

examples, 581–589

planning on, 637–638 nondeterministic Turing machine, 299 nondeterministic uncertainty, 448–450

criticisms of, 487–489 nondirectional backprojections, 696 nondominated, see Pareto optimal nonholonomic, 735, 791, 888, 893

nonholonomic constraints, 722

nonholonomic integrator, 741–742, 901,

908, 911, 915

showing it is nonholonomic, 902 steering, 917–918

nonholonomic metric, 811

nonholonomic planning, 13, 791–792

nonholonomic system, 827–828 nonholonomic system theory, 888–910 noninformative prior, 485–487

nonintegrable, 893

nonlinear optimization, 855

nonlinear programming, 855–857

nonlinear system, 741–742 affine in control, 890–892 affine-in-control, 741

nonparametric methods, 487 nonpositively curved space, 857 nonprehensile manipulation, 700–704

nonrigid transformations, 120

nonzero-sum game, 468–476

with more than two players, 475–476 with two players, 469–475

see also Nash equilibrium

NP (complexity class), 299 null sensor, 563

numerical continuation, 341 numerical integration

Euler, 813–814

multistep methods, 815

Runge-Kutta, 424, 814–815

single-step methods, 815

NURBS, 91

OBB, 211

observability, 740

observation space, 451, 561

observations, 451–454

obstacle region, 92, 155

in the C-space, 155–167 1D case, 158

general case, 164–167

polygonal case, 159–163

polyhedral case, 163–164 in the state space, 794–797 in the world, 82–92 polygonal case, 251–264

time-varying, 312–318

obstacles, 82

occupancy grid, 92, 684

Ochiai unknot benchmark, 351 octane transformations, 110–112

odd/even sensor, 561–562

odometric coordinates, 645, 660

odometry sensors, 605

on-line algorithm, 20, 672–673

open ball, 130

open set, 89, 128 open-loop

control law, 793

plan, 370

operator, 58

optical character recognition, 456–458 optimal motion planning, 357–364 optimal planning

discrete, 43–57

fixed-length plans, 45–50

unspecified length, 50–53

optimization, 438–441

orientation sensor, 600 oriented bounding box, 211 orienteering problem, 365

origami, 347

orthogonal group, 146

outdoor navigation, 362

painting, 354

parallel manipulator, 338

parallel-jaw gripper, 701

parameter estimation, 458–459

parameterization, 136, 391

Pareto optimal, 362–364, 440–441, 470,

471, 476, 484

parking a car, 13, 726, 744, 800, 860,

868, 898

part configuration space, 332 partial grid, 205

partial plan, 63

partially observable Markov decision pro- cess, see POMDP

particle, 747

dynamics, 747–752

falling, 767–768

on a sphere, 776–777 particle filtering, 618–619, 655

path, 139

path connected, 139

path tuning, 319

path-constrained phase space, 849 path-directed subdivision tree, 837 pattern classification, 455–458

pebble, 602

peg-in-hole problem, 692, 696–698

pendulum, 750–751

double, 785

Pennsylvania Turnpike, 441

perfect recall, 622

permissible action trajectories, 790 Pfaffian constraints, 720–721, 724, 734,

742, 775–777, 891–894, 897, 903,

920

pharmacophore, 351

phase constraints, 795

phase space, 735–744

obstacles, 794–797

path-constrained, 849–850

phase transition equation, 737, 738

phase vector, 736

Philip Hall basis, 907–908, 910–914, 917

Piano Mover’s Problem, 157–158, 789,

790, 817, 818, 832–835, 838, 841,

855

term, 169

total degree, 169

polynomial-time reducible, 300

POMDP, 589, 638–640

Pontryagin’s minimum principle, 515, 856,

875–879, 922

time-optimality case, 879

portiernia, 329–330

piecewise-linear obstacle motion, 313–314, position sensor, 600

317

pitch rotation, 98

plan-and-transform method, 842–846 plan-based state transition graph, 507 plan-space planning, 65

planar joint, 105

plane-sweep principle, 257–258

radial sweep, 263, 407

planetary navigation, 362

planner, 21

planning graph, 64–69

planning under sensing uncertainty, 633– 704

general methods, 634–640

manipulation, 691–704

pursuit-evasion, see visibility-based pursuit-evasion

see also SLAM

see also localization Poinsot, 754, 760

point robot, 252

point-location problem, 422, 830

policy iteration, 514–518

for reinforcement learning, 535 on an information space, 638 with average cost-per-stage, 527 with discounted cost, 526–527

polygonal model, 82–85, 251–264

face, 253

half-edge, 253

representation, 251–253

polyhedral model, 85–87

polynomial, 169–170

coefficient, 169

in formal Lie algebra, 912

positive definite function, 866 positive literal, 58

possibilistic uncertainty, see nondeter- ministic uncertainty

posterior, 443

potential energy, 766, 767, 769, 772

potential function, 191, 225, 766

attractive term, 225 continuous state space, 401 discrete, 375

repulsive term, 225

see also navigation function

PQP (Proximity Query Package), 245 predicate, 58

for geometric models, 85 preimage of a function, 131 preimage of a motion command, 695 preimage of an observation, 563 preimage planning, 692–700 Princess and the Monster, 627

principle of least action, see Hamilton’s principle of least action

principle of optimality, see dynamic pro- gramming

principle of virtual work, 776 principle subresultant coefficients, 290 prior distribution, 443, 484–487

prioritized planning, 322

prismatic joint, 100, 101, 103, 105, 107

Prisoner’s Dilemma, 472, 490 PRM, see sampling-based roadmap probabilistic completeness, 186

probabilistic information space, 577–581 approximations, 595–597

examples, 589

planning on, 638–640 probabilistic information state

computation of, 614–619

radial sweep, 263, 407

random loop generator, 343, 345

random sampling, 198–201

probabilistic roadmap, see sampling-based roadmap

probabilistic uncertainty, 448–450

of SO(3), 198–199

of directions, 199

tests, 200–201

criticisms of, 483–487

probability function, 442

probability measure, 193

probability space, 441–442

probability theory, 441–444

problem solving, 27 product of inertia, 758

projection sensors, 600–601, 605–608 projective geometry, 97

projective space, 138 protein cavity, 113

protein folding, 15, 353–354

proximity sensor, 601

pseudometric, 191, 314

pseudorandom number generation, 199– 200

linear congruential, 200

PSPACE, 299

Puma 560 robot, 107

pure strategy, 445

pursuit-evasion game, 627, 782, 783 visibility-based, see visibility-based

pursuit-evasion pushing a box, 731–732

Q-factor, 534

Q-learning, 534–535 quadratic cost functional, 874

quadratic potential function, 402 quantified variables, 282

quantifier, 282

quantifier-elimination problem, 283

quantifier-free formula, 282

quasi-static, 731

quaternion, 150–153

from a rotation matrix, 153 quotient topology, 136

radar map, 275–276

random variable, 444

random-walk planner, 228

randomized algorithm, 305

randomized lower value, 466, 542, 547

randomized plan, 538, 545

randomized potential field, 224–227, 402 under differential constraints, 837

randomized saddle point, 466 randomized security plan, 542 randomized strategy, 445–446 randomized upper value, 465 randomized value, 466, 542

range scanner, 604

range space (for discrepancy), 206 rapidly exploring dense tree, 228–237,

314, 325, 340, 348

exploration, 228–232

finding nearest points, 232–234 making planners, 235–237

under differential constraints, 832– 836

rapidly exploring random tree, see rapidly exploring dense tree

Rapoport, 490

rational decision maker, 460, 479, 481 RDT, see rapidly exploring dense tree reachability graph, 804–805

reachability tree, 802–804

reachable set, 798–801

backward, 865

for simple car models, 800 reactive plan, see feedback plan real algebraic numbers, 286–287 reality television, 478–479

reckless driving, 13

recognizability, 582, 696

reconfigurable robot, 330

recontamination, 688

reduced visibility graph, see shortest-path roadmap

Reeds-Shepp car, 725, 794, 800, 845

Reeds-Shepp curves, 884–886

refinement of a plan, 22, 841

reflex vertex, 261

region of inevitable collision, 796–797 regret, 450–451, 462

regret matrix, 450, 451

reinforcement learning, 527–535 evaluating a plan, 530–534 general framework, 528–530

terminology, 528

conditional Bayes’, 453

frequentist, 484

RLG, see random loop generator roadmap

directed, 315

general requirements, 250–251 maximum-clearance, see maximum-

clearance roadmap

sampling-based, see sampling-based roadmap

shortest-path, see shortest-path roadmap Robbins-Monro algorithm, see stochas-

tic iterative algorithm

reinforcement planning, see reinforcement robot displacement metric, 190

learning

relative value iteration, 527 repulsive vertex, 404

reroute path, 646

resolution, 201

resolution completeness, 186, 201, 224,

325, 805, 831, 836

under differential constraints, 805– 808

resultant

force, 754

moment, 754

robot-robot collisions, 319

Rock-Paper-Scissors, 490, 493

roll rotation, 98 rolling a ball, 733–734 rotation

2D, 95–97

3D with quaternions, 150–152 3D with yaw-pitch-roll, 98–100

RRT, see rapidly exploring dense tree Rubik’s cube, 4, 5, 17, 30

Runge-Kutta, see numerical integration, Runge-Kutta, 424

retraction method, see maximum-clearancRussell and Norvig, 27

e

roadmap

reverse-time system simulation, 816 revolute joint, 100, 101, 103, 105–108,

113, 114, 121, 124

reward, 528

reward function, 439

reward functional, 528

reward space, 480

Riemannian manifold, 766

Riemannian metric, 810–811

Riemannian tensor, 810

rigid-body dynamics, see dynamics, of a rigid body

rigid-body transformations, see transfor- mations, rigid body

Rimon, 375, 410 risk

saddle point, see sequential game, sad- dle point, and zero-sum game, saddle point

sample point of a cell, 255 sample sequence, 195

sample set, 195

sample space (of a probability space), 442

sampling-based neighborhood graph, 416 sampling-based planning

for closed chains, 340–347 philosophy, 185

time-varying, 314–315

under differential constraints, 810– 837

with feedback, 412–429, 837–841 sampling-based roadmap

ǫ-goodness, 240

analysis, 240–241

basic method, 237–241

boundary sampling, 243

bridge-test sampling, 243–244

Guassian sampling, 243

medial-axis sampling, 244

preprocessing phase, 238–239

query phase, 240

vertex enhancement, 242–243

visibility roadmap, 241–242

sampling-based roadmaps, 237–244 under differential constraints, 837

Sard’s Theorem, 411

SB, see strong backprojection scalarization, 364

scaling an object, 121 screw joint, 105

screw transformation, 106

sealing cracks, 7

search algorithms, 318

sensor feedback, 581

sensor mapping, 561, 591

sensor observation, 560

sensor-based planning, see planning un- der sensing uncertainty

sensorless manipulation, 701

sensorless planning, 582–585, 612–614 sensors

continuous, 598–605

discrete, 561–564

sequential game, 536–551

against nature, see game against na- ture, sequential

information space of, 619–627 Markov assumption, 496–497 more than two players, 550–551 on state spaces, 544–551

saddle point, 542–544, 546, 619, 621–

623, 626

zero-sum with nature, 549–550 shadow component, 674

adaptation to continuous spaces, 220– shadow region, 674

224

under differential constraints, 818– 820, 828–830

unified view, 41–43

see also backward search see also bidirectional search see also forward search

search graph, 41, 217, 818 searching an environment, 657

second-order controllable systems, 919 second-order differential drive, 744 second-order unicycle, 743

section (of a cylinder), 290 sector (of a cylinder), 290 security plan, 539–541, 546

security strategy, 461

randomized, 465

selective sensor, 562

semi-algebraic decomposition, 284

semi-algebraic model, 87–89

semi-algebraic set, 87

sensing history, 566

shearing transformation, 121

shooting methods, 856

shortest-path functional, 764

shortest-path roadmap, 261–264, 679

SICK LMS-200, 604

sigma algebra, 192

sign assignment, 284

sign sensor, 562

sign-invariant region, 284

silhouette curves, 293, 296

silhouette method, see Canny’s roadmap algorithm

simple polygon, 90

simple-car model, 722–726

two-car game, 783

with nature, 781

simple-unicycle model, 729–730

simplicial complex, 265–268 simply connected space, 141 Simpson paradox, 482

simulation-based dynamic programming,

see reinforcement learning

simulation-based methods, 528 simulation-based planning, see reinforce-

ment learning

simultaneous localization and mapping,

see SLAM, 656

single query, 186, 217

single shooting, 857

singular 0-simplex, 267

singular 1-simplex, 266

singular k-simplex, 267

singular arcs, 878

singular complex, 265–267

singular distribution, 895

singular matrix, 295

singular point of a distribution, 895 singular simplex, 266

singular value decomposition (SVD), 516 situation calculus, 69

skew symmetry, 904, 907

SLAM, 655–684

probabilistic, 679–684

sliding-mode control, 389

sliding-tile puzzle, 4, 5, 30

small-time local controllability, 722, 726,

845, 868–870, 883, 886, 888, 892,

903, 908–910, 921

smooth differential drive, 744 smooth distribution, 895

smooth function, 385

smooth manifold, 134, 390–398, 895

RPn, 394–395

Rn, 393

Sn, 393–394

Riemannian, 810–811

smooth structure, 393 smoothness of a function, 385 Sobol sequence, 208

Sod’s Law, 448

Sokoban, 301

solid representation, 81

solution in the sense of Filipov, 388 solution trajectory, 387, 398

span of vector fields, 895 spanning tree, 355

spanning-tree covering, 355–357

spatial constraints, 351

special Euclidean group, 147–148, 154 special orthogonal group, 146 speedometer, 601

spherical coordinates, 397

spherical joint, 105, 107, 113 spherical linear interpolation, 189 spine curve, 92

spiral search, 673

squeeze function, 702

squeezing parts, 701–704

SSM, see swath-point selection method stability of a system, 862–866

asymptotic, see asymptotic stability Lyapunov, see Lyapunov stability time-varying case, 864

uniform, 863

stable configuration space, 334 stage-dependent plan, 505

standard grid, 203

star algorithm, 159–161

star-shaped regions, 411

state estimation, 572–573

state history, 400

state mapping, 590

state space, 28

state trajectory, 372, 400, 788

state transition equation, 28, 29, 737,

738

state transition function, 28, 29 state transition graph, 29

state transition matrix, 502 state-nature mapping, 590, 591

state-sensor mapping, 591

state-space discretization, 828–832

stationary cost-to-go function, 51, 511,

512, 514

stationary differential equations, 387 statistical decision theory, 455 steering methods, 817, 910–922

piecewise-constant actions, 910–916 sinusoidal action trajectories, 917–

920

steering problem, 792

Stentz’s algorithm, 362, 662–667

stereographic projection, 293, 394

sticking, 693, 697, 699, 700

STLC, see small-time local controllabil- ity

stochastic control theory, see game against nature, sequential, 495

stochastic differential equation, 781 stochastic fractal, 231

stochastic iterative algorithm, 533, 534 stochastic shortest-path problem, 556 strange topology, 131

strategy, 452

STRIPS, 27, 58–63

strong backprojection, 504, 696

structure problem, 353

sub-Riemannian metric, 811

subgroup, 146

subjective probabilities, 485 subspace topology, 130–131 sufficient information mapping, 573 sufficient statistic, 573

Sukharev grid, 203

superquadric, 92

supremum, 201, 439 Sussmann and Tang, 887

swath, 229, 231, 803, 804, 809, 818

swath-point selection method, 231, 818

Swiss cheese, 141

switching boundary, 388

switching time, 878

symmetric systems, 793–794 symmetric Turing machine, 300 symmetry class, 644

symplectic manifold, 778

system, 715, 793

tem theory

nonlinear, see nonlinear system simulator, 813–816

see also differential models system vector fields, 891 systematic search, 32–33

tangent bundle, 384, 738, 895

tangent point, 854

tangent space, 384, 390, 396 on a manifold, 395–398

TangentBug, 670

Tarski sentence, 282

Tarski-Seidenberg Theorem, 286

Taylor series, 872, 873, 898, 899 TD, see temporal difference team theory, 626

temporal difference, 531–534

temporal logic, 364

termination action, 51, 568

THC, 17

theory of computation, 298 time scaling, 317, 792

time-invariant, 741

time-limited reachable set, 799 time-monotonic path, 313, 315–317

time-optimal trajectory planning, 853– 855

time-varying motion planning, 311–318 algebraic obstacle motion, 315 bounded speed, 315–316

unbounded speed, 312–315

timing function, 317

tire skidding, 761

Tit-for-Tat, 490

topological complexity, 429

topological graph, 132–134, 803 topological manifold, see manifold

determining whether controllable, 903–topological property, 845, 909

910

determining whether nonholonomic, 892–903

distribution, 895

linear, see linear system nonholonomic, see nonholonomic sys-

topological space, 128–134

connected, 139, 140

identification, 136

metrizable, 187

path connected, 139

simply connected, 141

topologist’s sine curve, 139 topology

manifold, see manifold

trivial topology, 131

Turing machine, 19, 299

two-point boundary value problem, 788,

topological space, see topological space torque, 751, 753, 771

torus, 137, 138, 143, 171, 172, 175

792, 798, 805, 810, 816–820, 823,

830–832, 834, 835, 837, 855–857,

861, 862, 867, 910

total differential, 778, 779

tower exponentiation, 304 Towers of Hanoi, 368 trailers, 730–731

trajectory, 387

trajectory optimization, 855–857 trajectory planning, 792

path-constrained, 846–855

transcription, 857

transfer mode, 334

transfer path, 335 transformations

2D chain, 100–103 2D rigid body, 94–97 3D chain, 103–112

3D rigid body, 97–100 general concepts, 92–94

kinematic tree, 112–120

nonrigid, 120–122

transit path, 335

transition configurations (mode change), 334

translating a disc, 94

trapezoidal decomposition, see vertical decomposition

trapped on a surface, 734–735 Traveling Salesman Problem, 354 tray tilting, 612–614, 701

triangle fan, 91

triangle inequality, 187

triangle model, 90–91

triangle strip, 91

triangular enumeration, 807

triangulation, 250, 266, 268–269, 307,

404

tricycle, 725

trim trajectory, 809 trivial operator, 66

Type A contact, see Type EV contact

Type B contact, see Type VE contact Type EE contact, 164, 167

Type EV contact, 161, 162, 164–166,

184

Type FV contact, 163, 167

Type VE contact, 161, 162, 164–166,

182, 184

Type VF contact, 164, 167

Udupa, 127 uncertainty

brief overview, 435–436

due to partial predictability, 435, 496–

535

due to sensing, 435, 559–627, 633–

704

underactuated system, 722, 793, 804, 827–

828

unicycle, 729–730, 743–744

uniform random, 198

union-find algorithm, 224, 239

unique point, 662

unit complex number, 149 unit quaternions, 150

unknot, 350

unsupervised classification, 455

unvisited states, 33

upper envelope, 467

upper value of a game, 461, 539, 546

utility function, 482–483 utility of money, 483 utility theory, 477–483

vacuum cleaning, 354

value iteration, 45

backward, see backward value itera- tion, 45–48

convergence issues, 511–514

forward, 48–50

relative, 527

with interpolation, 419–423

van der Corput sequence, 196–197, 204,

205, 207, 217, 238

variation of a function, 763 variety, 168, 170–171

for 2D chains, 171–176

for general linkages, 176–180 vector field, 381–390, 398, 719

equilibrium point, 862

normalized, 400

over a cell complex, 402–404 piecewise-smooth, 388–390

vector space, 382–383

Rn over R, 383 of functions, 383

velocity field, 386–387

velocity-tuning method, 317–318

vertex selection method, 217–220, 226–

228, 231

vertical decomposition, 253–258, 267–268,

319

3D, 270–273

violation-free state, 796

virtual human, 11

VisBug, 670

warping a path, 140 wavefront, 357

wavefront propagation, 378–379, 429

wavelet, 358

way point, 406

WB, see weak backprojection

weak backprojection, 504, 552, 696, 697

weighted-region problem, 362

Weiner process, 781

Whitney’s embedding theorem, 134, 136 with probability one, 196

word (sequence of motion primitives), 881

world, 81, 745

world frame, 94

worst-case analysis, 448, 507, 570 wrench (from mechanics), 754

yaw rotation, 98

zero-sum game, 459–468

matrix representation of, 460 randomized saddle point, 466–468 randomized value of, 466

regret in, 462

saddle point, 462–464

value of, 462

visibility graph, see shortest-path roadmap visibility polygon, 648

visibility region, 674

visibility roadmap, 241

visibility sensor, 604, 647

visibility skeleton, 649

visibility-based pursuit-evasion, 684–691 a sequence of hard problems, 686 complete algorithm, 687–690

problem formulation, 684–687

variations, 690–691

Voronoi diagram, 200

Voronoi region, 200, 208, 212–214, 618

Voronoi vertex, 202

VSM, see vertex selection method

wall clock, 605

wall following, 662