7.1Rule-based Symbolic Spatial Reasoning

Transformation and Pose Representation. Rigid-body relationships between sensors, objects, and mechanisms are elements of the special Euclidean group

where $\mathbf{R}\in SO(3)$ is a rotation and $\mathbf{t}\in\mathbb{R}^{3}$ a translation; composing them moves measurements across frames. Early robotics parameterized serial chains through the Denavit–Hartenberg convention [1147, 1148], which gives forward kinematics from a minimal set of link parameters. Lie-group formulations instead write motion as exponentials of screw axes, the product-of-exponentials representation [1142, 1143], which is coordinate-free and behaves well where the DH parameterization has discontinuities. Quaternions [1149, 1150] and dual quaternions [1151, 1152] give compact, numerically stable encodings of rotation and screw motion for calibration and sensor fusion.

Projective and Multi-View Geometry. Reasoning from images must recover 3D structure and camera motion from 2D measurements under perspective distortion and scale ambiguity. The constraint between corresponding points in two views is the epipolar condition

with $\mathbf{F}$ the fundamental matrix. The eight-point algorithm [102] solves for $\mathbf{F}$ linearly, Hartley’s normalization [1153] made it numerically stable, and Nistér’s five-point solver [1154] reaches the minimal case for calibrated cameras. Zhang’s homography-based calibration [692] removed the need for special rigs; the field is consolidated in [112], and structure-from-motion systems such as COLMAP [115] scale it to thousands of images, with RANSAC [101] enforcing the algebraic constraints against outliers throughout.

Jacobian and Differential Formulations. For motion rather than static configuration, the map from configuration to task space,

is differentiated to relate velocities,

and the Jacobian $\mathbf{J}(\mathbf{q})$ carries the information about feasibility, singularities, and controllability along a motion. Whitney’s resolved motion rate control [1155] used it to command Cartesian velocities without closed-form inverse kinematics; Nakamura’s damped least squares [1156] trades exactness for stability near singularities; redundancy resolution [1157, 1158] uses null-space motion for secondary objectives; and Khatib’s operational-space formulation [1159] separates task and null-space dynamics so that objectives are written directly in task space.

Visibility and Coverage Geometry. What a sensor at pose $p$ can observe is the set

with $\mathcal{E}$ the environment and $\mathcal{O}$ the obstacles. The Art Gallery theorem [1160, 1161] bounds the number of viewpoints needed for full coverage; polygon visibility [1162] and shortest-path queries [1163] made the computations algorithmic; and Tarabanis et al. [1164] cast sensor planning as geometric optimization over fields of view modeled as cones, frusta, or polygons.

Workspace and Reachability Analysis. The reachable workspace of a mechanism is

with $\mathcal{C}_{\mathrm{free}}$ the feasible configuration space. Roth [1165] and Gosselin [1166] added performance and dexterity measures so that manipulability is characterized along with reachability; Merlet [1167] classified workspace types; Zlatanov et al. [1168] analyzed constraint-induced singularities; and sampling-based reachability maps [1169] trade closed-form guarantees for empirical coverage in high-dimensional systems.

Contact and Grasp Geometry. Whether a set of contacts can hold an object is decided in wrench space. Ferrari and Canny [1170] model the forces each contact can apply as a convex set of wrenches $\mathcal{W}$; the grasp is force-closed if

so that any external wrench can be resisted. GraspIt! [1171] made these metrics computable for arbitrary hands and objects; task-oriented measures [1172] weight the wrench space by what the task requires; and Dex-Net [336] samples analytic grasps at scale to train data-driven grasp predictors that keep the geometric criterion as their label.

Physics Engines. MuJoCo [1187], Bullet [1188], ODE [1189], and DART [1190] integrate rigid-body dynamics with contact by time stepping, and they resolve contact in one of two ways. Penalty methods treat a contact as a compliant spring-damper that resists interpenetration,

with penetration depth $\delta_{k}$, stiffness $k_{p}$, and damping $k_{d}$, and regularize friction similarly; they are cheap and simple, but stiff parameters destabilize the integration and soft ones introduce artificial compliance, which is acceptable in graphics and approximate planning but not in control. Constraint-based methods enforce Eq. (7.11) directly as complementarity constraints [1191], solved per step as a linear or nonlinear complementarity problem [1192], a convex quadratic program [1193], or a second-order cone program for exact friction cones [1194] (projected Gauss–Seidel and sequential-impulse schemes are the usual implementations). They give physically consistent, nearly penetration-free contact forces at higher cost and with harder scaling in the number of contacts, so engines in practice hybridize: hard constraints on normal forces, regularized tangential friction, warm starting, contact aggregation, and stabilization terms.

Analytic Quasi-Static Models. For the three settings of Figure 7.2, closed-form criteria replace simulation. At a point contact the admissible forces form the friction cone

which a polyhedral approximation turns into linear constraints. Mapping each contact’s cone through its moment arm into wrench space and taking the convex hull gives the grasp wrench space, and the grasp is force-closed when the origin lies strictly inside it, Eq. (7.8) [265]; form closure is the stronger, purely geometric condition in which contact geometry alone prevents motion, and the Ferrari–Canny $\epsilon$-metric (the distance from the origin to the hull boundary) grades grasp quality. For planar pushing the limit surface relates the applied wrench to the resulting slip, and its ellipsoidal approximation yields a motion cone of object velocities reachable from a given push, the basis of stable pushing and closed-loop push planning. For stacking, stability under gravity requires that the gravitational wrench be balanced by the supporting contacts [1195]: without friction, the center of mass must project into the support polygon; with friction, the contacts’ friction cones must generate a wrench cone containing the gravitational wrench.

Visibility and Line-of-Sight Graphs. Connecting configurations that can see each other reduces shortest-path planning to graph search with interpretable waypoints. The visibility graph of Lozano-Pérez and Wesley [1205] links obstacle, start, and goal vertices and recovers exact Euclidean shortest paths in polygonal environments by Dijkstra or A*; the configuration-space construction via Minkowski sums [1206] extends it to robots of finite size by growing the obstacles instead of shrinking the robot; continuous-Dijkstra algorithms settle the complexity at $O(n\log n)$ [1207, 1208]. Grid planners bring line-of-sight into the search itself: Field D* interpolates across cell faces for smooth, replannable paths [1209], Theta* updates parents by visibility to produce near-Euclidean paths on the fly [1210], and Jump Point Search prunes symmetric expansions by jumping between visibility events [1211].

Clearance-Oriented Skeletons. Where safety matters more than length, free space is retracted to a skeleton that keeps connectivity and maximizes distance to obstacles. Voronoi diagrams and medial axes give maximal-clearance paths, with Fortune’s sweepline [1212] for efficient planar construction; the generalized and hierarchical Voronoi graphs [1213, 1214] let a robot follow ridges with its sensors and build the clearance roadmap incrementally while detecting junctions and loops; and distance-transform updates [1215, 1216] maintain the skeleton in dynamic environments for real-time replanning.

Decomposition Graphs and Coverage. Discretizing space into cells trades geometric fidelity for simplicity and completeness. Occupancy grids [79, 1217] are probabilistic cell maps updated from range data on which planning is grid search; exact decompositions serve coverage, with boustrophedon decomposition [1218] partitioning free space into monotone cells and ordering them through an adjacency graph for complete, low-redundancy sweeps; and the coverage literature is systematized in [1219].

Sampling-Based Roadmaps and Trees. In high-dimensional configuration spaces, the graph is discovered by sampling. Probabilistic roadmaps [1220] sample and connect configurations in a preprocessing phase amortized over many queries and are probabilistically complete; RRT and RRT-Connect [1221, 1222] grow trees toward unexplored regions for single-query planning under kinematic and kinodynamic constraints; PRM* and RRT* [1223] add connection-radius and rewiring rules that make them asymptotically optimal; and FMT* and BIT* [1224, 1225] combine batch sampling with dynamic programming and heuristic search over increasingly dense implicit graphs for faster, anytime convergence.

Optimal, Any-Angle, and Incremental Graph Search. On a given graph, Dijkstra’s algorithm and A* [70, 66] are the optimal single-source and heuristic searches; LPA* [1226] and D* Lite [1227] repair a shortest path incrementally as edge costs change; and the any-angle planners above (Field D*, Theta*, JPS) improve path quality without giving up the discrete search.

Multi-Agent and Hierarchical Graph Reasoning. With several agents on one graph, coordination is search over a time-expanded network. Conflict-Based Search [1228] splits the problem into a high-level search over conflict constraints and low-level single-agent planning and is complete and optimal; ICTS [1229] searches joint cost allocations backed by individual searches; ECBS and EECBS [1230, 1231] are bounded-suboptimal with focal heuristics and better conflict handling; and SAT or ILP compilations [1232, 1233] reach global optimality on moderate fleets at the cost of solver scalability. Hierarchical and multi-resolution planning [1234] and contraction hierarchies [1235] precompute abstraction layers that answer shortest-path queries on continental road networks in well under a millisecond, with standardized maps and instances [1236, 1237] for comparison.

Constraint Programming (CSP/CP). When the decisions are combinatorial (which object, which placement, which grasp) but each must pass a geometric test, constraint programming encodes the choices as variables under constraints and interleaves symbolic branching with propagation, pruning, and geometric checks. Lozano-Pérez and Kaelbling [1249] cast task-and-motion planning as constraint satisfaction over action skeletons, pruning symbolic branches as soon as a geometric feasibility test fails; Lagriffoul et al. [1250] propagate and filter continuous domains before any expensive collision or IK call, so that many failures become cheap inconsistencies; and Dantam et al. [1251] interleave discrete search with incremental feasibility queries that reuse information across related constraints.

SAT/SMT Compilations. Compiling planning and feasibility into Boolean formulas, or into formulas over richer theories such as real arithmetic, puts clause learning, incremental solving, and conflict-driven pruning to work. dReal [1252] decides nonlinear real arithmetic up to a numerical tolerance ($\delta$-completeness), which gives certified answers where exact decidability is impossible; SMT-based planning for hybrid systems [1253] reasons first over an abstraction and adds constraints as counterexamples appear; SAT encodings of multi-agent pathfinding [1232] obtain optimal schedules on time-expanded graphs (the MAPF problem itself is treated in §7.1.3); and SMT over linear real arithmetic extends the encodings to continuous time and to robustness against execution delays [1254, 1255].

Mixed-Integer Formulations (MICP/MILP). When discrete mode choices (which region, which contact mode, which precondition) interact with continuous geometry and dynamics, binary variables encode the nonconvex choice and convex constraints capture feasibility within a mode. IRIS [1256] inflates large convex obstacle-free regions that serve as certified safe sets, turning collision avoidance into membership constraints with explicit margins; Graphs of Convex Sets [1257] compile motion planning through clutter into a shortest-path problem over convex nodes and edges that convex optimization, with mixed-integer selection where needed, solves with certificates; and later work constructs convex sets directly in configuration space and in space-time [1258, 1259]. In each case a globally nonconvex feasibility problem is replaced by a sequence of convex ones without giving up the guarantee.

Trajectory Optimization. Even with the task fixed, an executable motion must satisfy kinematic limits, collision avoidance, smoothness, and often dynamics, which is a continuous, usually nonconvex, constrained optimization whose local optimum comes with optimality conditions and sensitivities. CHOMP [1260] deforms an initial path by functional gradient descent on a signed-distance field; STOMP [1261] replaces the gradient with stochastic perturbations to handle non-smooth costs and local minima; TrajOpt [1262] solves a sequence of convex programs with hinge-loss collision penalties; and GPMP2 [1263] writes planning as inference on a sparse factor graph with Gaussian-process priors, which gives scalability and incremental replanning. Increasingly these optimizers run inside the safe sets of IRIS and GCS, which supply initialization, constrain the search, or verify the result.

Inverse Kinematics as a Constraint Subproblem. “Is there a joint configuration that reaches this pose under limits and collisions?” is the most frequent feasibility query in any hybrid planner, so IK solvers are built as fast oracles. IKFast [1264] derives closed-form solutions and generates optimized code for repeated real-time queries; TRAC-IK [1265] combines complementary numerical strategies to raise the solve rate and avoid stalling the planner above it; and global IK by mixed-integer programming [1266] returns certifiable solutions for full chains when a feasibility proof is needed.

Hybrid Logic–Geometric Planning. In long-horizon problems the discrete decision (what to do next) and the continuous one (how to do it) cannot be separated, and task-and-motion planners close the loop between them. Logic-Geometric Programming [1267, 1268] couples symbolic action sequences to bound-constrained nonlinear programs through a multi-bound tree search, so that continuous feasibility and cost decide which symbolic branches are worth expanding; PDDLStream [1269] integrates black-box geometric generators (grasps, placements, motions) into symbolic planning by optimistic refinement, requesting continuous witnesses only when needed while remaining complete under suitable stream assumptions; R-LGP [1270] biases the search with reachability guidance; and COAST [1271] uses constraints to communicate between task planner and stream generators, cutting wasted geometric proposals by an order of magnitude in planning time.

Classical Symbolic Planning (STRIPS/PDDL and Heuristic Search). STRIPS [67] fixed the representation: planning as search over symbolic states with action schemas, so that a plan can be checked against the model and the continuous motion layer sits behind a clean abstraction boundary. PDDL [1280] standardized domain and problem specification so that planners could be compared across navigation, logistics, and assembly, with extensions (ADL, numeric fluents, temporal constructs) that capture robotic requirements without abandoning explicit semantics. Graphplan [1281] builds a planning graph whose mutual-exclusion constraints prune incompatible action combinations early, and FF [1282] made forward search fast with relaxed-plan heuristics that ignore delete effects, which capture ordering constraints such as unstacking before stacking in object-rich domains. Task-and-motion planning (§7.1.4) extends these planners with geometric feasibility checks [1283, 1284, 1285]; the common pattern is to keep the symbolic reasoning explicit, delegate feasibility to motion and IK solvers, and wrap the plan in an execution structure with monitors and recovery.

Finite-State Machines and Reactive Mode Switching. An FSM switches among a few well-defined behaviors (navigate, align, grasp) with explicit transition guards, which makes it transparent and fast but prone to state explosion as contingencies multiply. Statecharts [1286] add hierarchy and concurrency, so that complex controllers are nested reusable submachines with precise semantics; Brooks’ subsumption architecture [81] layers behaviors so that higher ones override lower ones, a blueprint for composing navigation and avoidance without global planning, systematized as behavior-based robotics [62]; teleo-reactive programs [1287] evaluate conditions continuously and fire the highest-priority satisfied rule; and ROS tooling such as FlexBE [1288] provides hierarchical, event-driven state machines at deployment scale.

Behavior Trees. A behavior tree re-evaluates its conditions on every tick and chooses among structured alternatives (sequence, fallback, parallel), so that long-horizon execution survives disturbances without committing to one fixed sequence; subtrees encapsulate reusable routines, guards and fallbacks trigger immediate recovery, and the composition semantics fit perception and motion skills. BTs originated in game AI [1289]; Marzinotto et al. [1290] formalized their semantics and their relation to other switching structures, and Colledanchise and Ögren [1291, 1292] showed which compositions preserve safety and robustness and consolidated the design principles. Compiling or wrapping a symbolic plan into a BT keeps the nominal task structure while exposing runtime guards and recovery branches [1293]; ARIAC systems pair PDDL planning with BT execution monitors to handle failures, occlusions, and defective parts [1294]; and event-driven BTs [1295] react to non-periodic stimuli rather than waiting for the next tick.

Logic-based Execution and Production Rule Systems. A production system keeps a working memory of facts and fires forward-chaining rules when their conditions hold, which suits event-condition-action policies, mode switching, and safety enforcement (no-go zones, mutual exclusions, priorities) and depends on fast incremental matching. OPS5 [1296] set the model; the Rete algorithm [1297] caches partial matches so that large rule sets update in milliseconds as facts change; CLIPS [1298] made the toolchain portable; and Soar [1299] integrated large rule bases with planning and execution in one architecture. In robotics, KnowRob [1300] and CRAM [1301, 1302] join symbolic knowledge to rule-driven execution for reasoning about actions, effects, and everyday manipulation, and LTLMoP [1303] compiles temporal-logic specifications into correct-by-construction reactive controllers whose safety and sequencing constraints are explicit at the program level.

Structural Causal Models and Counterfactuals. An SCM makes mechanisms explicit (“clearance determines collision risk”, “traffic density sets delay”) and separates intervention from observation: the $do(\cdot)$ operator replaces a structural equation instead of conditioning on a value, which is what is needed when, say, congestion and delay are both driven by time of day. Spatial pipelines typically start from a graph fixed by temporal precedence and locality priors (edges among nearby regions, interacting agents, adjacent cells), estimate the mechanisms from data, and validate them against implied conditional independences and refutation tests [1313]. Counterfactuals follow the abduction-action-prediction recipe: infer the exogenous noise consistent with the observed trace, apply the hypothetical intervention, predict the outcome [1312]. DoWhy and DoWhy-GCM [1314, 1315] implement identification, estimation, and refutation for this workflow on real spatiotemporal data.

Causal Discovery: Constraint- and Score-Based. When the graph is unknown but observational data are plentiful, constraint-based methods read structure off conditional independences: the PC algorithm builds the skeleton by independence tests and orients what it can, returning a Markov equivalence class, and FCI [1316] handles latent confounding and selection bias by returning a partial ancestral graph. Score-based methods instead search graph space under an objective such as BIC: GES [1317] greedily adds and then removes edges over equivalence classes, and its forward-backward structure often recovers mesoscale organization such as bottlenecks that drive downstream congestion. Spatial data strain both. Large conditioning sets are expensive and statistically weak, so practice restricts conditioning to a radius or $k$-hop neighborhood, forbids edges that violate adjacency or reachability priors [1318], and uses order-independent variants (PC-stable [1319]) whose high-dimensional consistency is understood [1320]; ambiguous orientations are then resolved by targeted interventions. causal-learn [1321] and the TETRAD / Py-Tetrad implementations of FGES [1322, 1323] provide these pipelines at facility and city scale.

Independent-Noise Discovery (LiNGAM). In linear-Gaussian settings many edge directions are unidentifiable from independences alone. LiNGAM [1324] assumes a linear structural model with independent non-Gaussian noise, under which the causal ordering is identifiable, and DirectLiNGAM [1325] estimates it by regression rather than ICA. Spatiotemporal signals need care because autocorrelation and smoothing push the noise toward Gaussian; temporal blocking, prewhitening, and locality constraints are the usual remedies, and the recovered ordering then scaffolds an SCM for intervention analysis.

Causal Action Languages and Plan-Space Causal Links. Much causal structure in robotics is designed knowledge rather than discovered: actions have direct and indirect effects, and the system must reason about change under incomplete information. The action language C⁺ [1326] writes causal theories of action with inertia and nonmonotonic semantics, compactly describing how fluents such as occupied(c) or visible(a,o) evolve; CCALC [1327] compiles them to SAT or ASP so that prediction, diagnosis, and plan synthesis use the same solvers; and multi-valued fluents and external geometric predicates (collision checks, IK) are being integrated without abandoning the formal semantics [1328]. In plan space, partial-order causal-link planning [1329] represents a plan as partially ordered actions plus links $A\xrightarrow{p}B$ (action $A$ establishes precondition $p$ for $B$), which makes threats explicit and repairable by promotion, demotion, or binding constraints; UCPOP [1330] extended the representation to ADL and conditional effects and VHPOP [1331] added heuristics and reachability analysis. In spatial domains a causal link is often a physical dependency, “unblock door” enabling “move cart”, which bridges symbolic causality and spatial feasibility.

Execution and Verification. A causal plan must be realized in time and checked. Simple temporal networks [1332] enforce difference constraints between events with polynomial consistency and dispatchable forms [1333], and STNUs with dynamic-controllability analysis [1334] handle contingent durations, so that ordering and clearance constraints stay satisfiable under bounded disturbance. The SAT/SMT machinery of §7.1.4 enters here as an explanation device: when a schedule is unsatisfiable, the unsat core is a minimal set of conflicting commitments, a concrete statement of which decisions caused the failure [1232, 1233]; and for hybrid dynamics $\delta$-complete SMT (dReal) [1252] and dReach [1335] verify safety and synthesize interventions with numerically sound proofs or counterexamples.