cs.ROOct 23, 2026
SaveNeuromorphic Decision Dynamics for Deadlock-free Safe Navigation in Congested Environments
Organizations: Department of Mechanical and Aerospace Engineering, Princeton University, NJ, USA. · Department of Electrical and Computer Engineering, Michigan State University, MI, USA.
Abstract
Safe navigation in congested environments requires both collision avoidance and coordinated passage. We introduce neuromorphic decision dynamics (NDD), a decentralized, event-based controller, that provides navigation in congested spaces with guarantees on safety, liveness, robustness, and scalability. NDD makes safe-and-live deconfliction a controllable, locally tunable emergent property of local agent interactions, without requiring communication, preassigned priorities, models of neighbors' objectives or future actions, or estimates of group size or global network properties. By design, NDD couples the dynamics of internal decision and attention states with changing physical states and locally observed relative motion. Each agent continuously modulates its speed along its prescribed path, responding as soon and as much as conflict resolution requires. Agents self-organize into disjoint, locally engaged groups that resolve conflicts concurrently. When any group's conflict becomes safety-critical, decision-action feedback destabilizes collective indecision, and coordinated conflict-resolution emerges that stabilizes a safe traversal order within the group. Order persists as conflicts clear, but groups may split or merge as agents autonomously adapt to new conflicts and those with resolved conflicts resume their nominal motion. We derive explicit conditions on sensing range, feedback gains, response time scales, and actuation limits that guarantee collision avoidance and traversal-order formation in finite time with no deadlock or livelock for finite, heterogeneous agent populations of arbitrary, changing size. Computational cost scales with the number of local interactions sensed by each agent. Large-scale simulations, comparisons with existing approaches, and hardware experiments demonstrate NDD in complex congested scenarios and validate its scalability.
Figures & tables
Fig. 1 : Emergence of safe-and-live deconfliction under an NDD-driven controller. (A) Colored bodies show six agents at time ; faded poses project motion along prescribed paths at equally spaced future times, assuming current speeds persist. Closer spacing indicates slower motion. Dotted portions show motion after projected conflict clearance. (B) An arrow means agent ’s motion influences agent ’s conflict evidence. Darker edges indicate stronger influence; node size represents aggregate conflict-evidence magnitude . (C) Decisions initially indicate collective yielding, then differentiate. The bracket marks negotiation time ; shading identifies negotiation, hold, and release. (D) Realized speeds track decision-dependent commands. Positive and negative decisions raise and lower commanded speeds, respectively, relative to nominal (horizontal dashed line). (E) The differentiated decision magnitude , with mean , spikes during negotiation, persists during hold, and vanishes during release. (F) The mean decision becomes negative during collective yielding, then returns to near zero during hold while decision differences persist. After release, decisions vanish and speeds return to nominal. Vertical dashed lines in C–F mark snapshot time .
Fig. 2 : Multitime scale embodied control architecture for safe-and-live deconfliction . All layers operate concurrently at distinct characteristic time scales. The slow planning layer supplies a prescribed path and nominal motion command . At a fast sensing and processing rate, the perception layer constructs the egocentric observation from onboard measurements of the agent’s own motion and its neighbors’ relative motion, without communication. These observations drive the fast decision and control layer: conflict evidence drives decision state , while attention state regulates the response. The map continuously adjusts commanded speed above or below nominal while retaining the nominal angular-rate command. Low-level tracking dynamics execute these evolving references through the actuators, so decision formation, attention adaptation, and physical action co-evolve. The resulting motion changes inter-agent geometry on the slower physical-interaction time scale. These changes generate new measurements that feed back into the ongoing decision dynamics, closing the continuous decision-action-perception loop.
Fig. 3 : Contested-region construction from instantaneous local kinematics. (A) The dashed rays extend the currently measured velocity directions and are instantaneous heading projections; the physical paths may subsequently smoothly curve. The intersection of the rays defines the geometric crossing point and crossing angle . On each projected ray, the markers and delimit the segment over which simultaneous occupancy can reduce inter-agent separation below . Together, these segments define the contested region. The current along-ray distances and speeds determine the projected entry and exit times and hence the occupancy intervals of the two agents. Conflict evidence depends on possible temporal overlap of these intervals and does not require equal arrival at . (B) The right-triangle constructions locate the upstream segment boundaries. The perpendicular clearance satisfies , giving . Shallower crossing angles therefore produce longer contested segments and, for a fixed speed, longer projected occupancy intervals.
Fig. 4 : Graph hierarchy from local sensing to locally engaged groups. (A) Agent 2 evaluates the egocentric sensed-interaction set . Under the convention , an arrow indicates that agent ’s motion enters agent ’s evidence. Solid arrows are the current conflict interactions . Dashed gray double-headed links denote mutually sensed but nonconflicting pairs–the dashed gray edge from agent 2 belongs to . (B) The weighted directed conflict graph contains the reciprocal pair and generated by every physical-conflict pair . For , arrow thickness represents the directional weight , so reciprocal directions may have unequal weights. The – conflict illustrates pronounced asymmetry: taking and , the graph depicts . Dashed gray double-headed links are mutually sensed nonconflicting pairs shown for context and do not belong to . (C) The strongly connected components of are the locally engaged groups. The dashed box highlights the component containing agent 2. Sensed nonconflicting interactions do not merge these components.
Fig. 5 : Conflict release smoothly reconfigures the selected differentiated response. Left graphs show reciprocal interaction sensitivities; right graphs show traversal orders, with arrows from the agent selected to pass first to its follower. Coordinates and describe decision differences in ; represents equal decision changes. The unit dominant eigenvector of the interaction-sensitivity matrix determines the decision pattern; is its signed amplitude and measures offset from the instability threshold. (A) Before clearance ( ), all pairs are in conflict. Initial decisions separate into common and differentiated components, and . Positive initial amplitude selects the upper attracting branch. Blue and red curves denote attracting and unstable equilibria, respectively; the inset shows their stability exchange at . (B) After conflict – clears ( ), the inherited state decomposes into along the updated dominant eigenvector and the perpendicular remainder . States evolve continuously as the dominant eigenvector rotates and the equilibrium amplitude decreases. Agent 3’s decision becomes positive; orders and permit agents 1 and 3 to progress concurrently. Pale elements show the previous configuration; the dashed – interaction indicates residual sensitivity. Supplementary Sec. S8 provides the matrices, amplitude model, and calculations.
Fig. 6 : NDD remains safe and on-path as congestion increases. Methods are compared using homogeneous Dubins-car agents in the same 50 randomized start–goal scenarios per population size, (minimum crossing angle ). Points are means over scenarios for each method and population size; error bars are bootstrap confidence intervals. (A) Safe-agent success is the percentage of agents reaching their goals without a safety violation. NDD maintains success, whereas the success rate of LivePoint, the strongest baseline by this measure, remains below and declines as congestion increases. (B) Mean minimum pairwise separation versus mean time per agent to reach its goal. Marker size denotes population size; the dotted line marks the m safety threshold. NDD retains a safe separation margin across all group sizes, although its completion time increases with population size. Shorter baseline times should not be interpreted as faster safe-and-live deconfliction when separation falls below the safety threshold. (C) Mean deviation from prescribed paths. NDD maintains zero deviation, resolving conflicts through speed modulation rather than spatial detours. The panels distinguish safe completion from goal attainment alone and show that baseline path deviation does not ensure safety in these tests.
Fig. 7 : NDD enables safe-and-live deconfliction through shared crossing regions. Panels show Dubins-car agents with unlimited sensing range and nominal speed m/s. (A to D) Near-antipodal exchange, with agents starting around a circle and moving toward roughly opposite goals. (E to H) Intersecting groups of approximately parallel paths. Columns compare NDD (A and E), ORCA (B and F), LivePoint (C and G), and decentralized CBF-QP (D and H) using the same start–goal configuration within each row. Colors identify agents; filled and open circles mark starts and goals, respectively. Small dots mark positions at s intervals, so closer spacing indicates slower motion. Crossed circles mark pairs whose separation fell below the m safety distance; insets enlarge the corresponding regions. NDD-controlled agents remain collision-free in both scenarios while following their prescribed straight paths: spatial path intersections need not cause collisions because agents can traverse the same region at different times by modulating their speeds to create temporal separation. In contrast, ORCA, LivePoint, and decentralized CBF-QP record 9, 6, and 16 colliding pairs in the top row and 20, 15, and 41 in the bottom row, respectively.
Fig. 8 : Emergent traversal order and continuous adaptation in six-robot experiments. Six TurtleBot3 robots follow prescribed paths without inter-robot communication. Columns show decisions , measured speeds , and planar trajectories; colors identify robots. Positive and negative decisions raise and lower commanded speeds relative to nominal. (A to F) Two antipodal repetitions with initial positions differing by – cm per robot produce traversal orders (A to C) and (D to F). Robot 2 (orange) passes first in one trial and last in the other, illustrating how small motion asymmetries can be collectively amplified into distinct traversal orders without preassigned priorities. (G to I) In orthogonal crossings, robots 3 and 6 switch from yielding to speeding up at different stages of the encounter, illustrating continuous adaptation of their responses. (J to L) Mixed lanes show differentiated speed adjustments across multiple intersections. Across trials, decisions relax toward zero as robots complete their crossings. Gray dotted lines mark nominal speed . Trajectories darken with distance traveled; circles and crosses mark recorded starts and ends.
Fig. S1 : Bifurcation diagrams and unfolding by timing bias. Equilibrium branches illustrate the scalar critical equation ( S37 ) with and . The horizontal axis shows , the offset of the dominant eigenvalue of the interaction-sensitivity matrix from the instability threshold . The vertical axis shows , the signed amplitude of the differentiated decision pattern along the dominant eigenvector ; its equilibrium value appears in Equation ( 10 ). Solid blue and solid red denote stable ( ) and unstable ( ) equilibria, respectively, where is evaluated at each equilibrium. (A) The positive-cubic model includes a negative quintic term that stabilizes the outer branches. Folds connect stable and unstable segments, allowing multiple stable responses to coexist. (B) The negative-cubic model provides cubic saturation without a quintic term. Left column: With timing bias , the nonzero quadratic coefficient produces a transcritical exchange of stability at in both models. Right column: A positive timing bias unfolds the crossing, removes the equilibrium at , and biases the response toward positive amplitude without eliminating all competing stable equilibria. These coefficients illustrate possible branch geometries and are not derived for a specific controller.
| Symbol | Definition |
|---|---|
| ; | Agent indices; instantaneous follower and leader, respectively, in an ordered interaction. |
| , | Agent ’s position and velocity vector; is the scalar traversal speed. |
| , | Agent ’s decision and attention states. Positive decisions favor speeding up; negative decisions favor slowing down. |
| , | Agent ’s nominal and commanded traversal speeds. |
| , | Lower and upper admissible traversal speeds of agent ; bounds realized motion, including tracking and actuation transients. |
| State of the fast decision–attention–speed subsystem, comprising decisions, attention states, and realized traversal speeds. |
Table S1 : Notation: agent states and controller parameters. Bold symbols denote vectors or matrices; a dagger denotes a differentiated fast subsystem equilibrium.
| Symbol | Definition |
|---|---|
| , | Sensed neighbors and sensed directed interactions of agent ; . |
| , | Reciprocal directed interactions. Under the edge convention , agent ’s motion influences agent ’s evidence. |
| , | Unordered physical-conflict pairs and their associated directed interactions. These exclude cleared pairs, even if still sensed. |
| , | Weighted directed physical-conflict graph and its agent set. |
| , | Index set of strongly connected components of the conflict graph and component . Each component is a locally engaged group. |
| , | Agents and unordered physical-conflict pairs in group . |
Table S2 : Notation: interaction structure and conflict evidence.
| Symbol | Definition |
|---|---|
| , | Required minimum spatial separation and sensing radius. |
| , | Projected crossing point and crossing angle. |
| Half-length of a contested segment, . | |
| , | Projected closest-approach distance and time. |
| , | Spatial and temporal proximity buffers in the pressure map. |
| Agent ’s remaining distance to its contested-segment entry boundary. |
Table S3 : Notation: conflict geometry, timing, and safety.
| Symbol | Definition |
|---|---|
| Sensitivity of conflict evidence to decision-induced speed changes at frozen conflict geometry and interaction topology; not a frozen interaction-weight matrix. | |
| , , | Common projected time until the agents reach their respective contested segments at a group tie, its absolute upper bound, and its positive lower bound for safety-critical reference observations, respectively. |
| , | Dominant eigenvalue of and associated eigenvector defining the leading-order collective decision pattern. |
| Spectral threshold for loss of stability of collective indecision. | |
| Distance from the spectral threshold in the local critical equation. | |
| , | Critical-mode amplitude and differentiated equilibrium of the fast subsystem with state . |
Table S4 : Notation: spectral and bifurcation quantities.