Neuromorphic Decision Dynamics for Deadlock-free Safe Navigation in Congested Environments
Authors: Himani Sinhmar, Vaibhav Srivastava, Naomi Ehrich Leonard
Organizations: Department of Mechanical and Aerospace Engineering, Princeton University, NJ, USA. · Department of Electrical and Computer Engineering, Michigan State University, MI, USA.
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 t ; 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 i→j means agent j ’s motion influences agent i ’s conflict evidence. Darker edges indicate stronger influence; node size represents aggregate conflict-evidence magnitude ∣hi(t)∣ . (C) Decisions zi(t) initially indicate collective yielding, then differentiate. The bracket marks negotiation time Tneg ; shading identifies negotiation, hold, and release. (D) Realized speeds vi(t) track decision-dependent commands. Positive and negative decisions raise and lower commanded speeds, respectively, relative to nominal vnom=1m/s (horizontal dashed line). (E) The differentiated decision magnitude ∥z(t)∥=∑i=16(zi(t)−zˉ(t))2 , with mean zˉ(t)=61∑i=16zi(t) , 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 t .
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 Uinom=(ψinom,vinom) . At a fast sensing and processing rate, the perception layer constructs the egocentric observation Xi(q,v) 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 h(Xi) drives decision state zi , while attention state ui regulates the response. The map V(zi) 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 qce and crossing angle αe . On each projected ray, the markers i−,i+ and j−,j+ delimit the segment over which simultaneous occupancy can reduce inter-agent separation below dsafe . 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 qce . (B) The right-triangle constructions locate the upstream segment boundaries. The perpendicular clearance satisfies dsafe=rcesinαe , giving rce=dsafe/sinαe . 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 E2(t) . Under the convention e=(i,j) , an arrow i→j indicates that agent j ’s motion enters agent i ’s evidence. Solid arrows are the current conflict interactions E2(t)∩Econf(t) . Dashed gray double-headed links denote mutually sensed but nonconflicting pairs–the dashed gray edge from agent 2 belongs to E2(t)∖Econf(t) . (B) The weighted directed conflict graph G(t)=(V(t),Econf(t),ω(t)) contains the reciprocal pair (i,j) and (j,i) generated by every physical-conflict pair {i,j} . For e=(i,j) , arrow thickness represents the directional weight ωie(t) , so reciprocal directions may have unequal weights. The 2 – 7 conflict illustrates pronounced asymmetry: taking e=(7,2) and eˉ=(2,7) , the graph depicts ω7e(t)≫ω2eˉ(t)>0 . Dashed gray double-headed links are mutually sensed nonconflicting pairs shown for context and do not belong to G(t) . (C) The strongly connected components {Gc(t)}c∈C(t) of G(t) 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 ξ1=(z1−z2)/2 and ξ2=(z1+z2−2z3)/6 describe decision differences in D=c⊥ ; c=(1,1,1)T/3 represents equal decision changes. The unit dominant eigenvector ϕmax of the interaction-sensitivity matrix A determines the decision pattern; a is its signed amplitude and μ=λmax−λ∗ measures offset from the instability threshold. (A) Before clearance ( − ), all pairs are in conflict. Initial decisions separate into common and differentiated components, zˉ0c and z0 . Positive initial amplitude a0 selects the upper attracting branch. Blue and red curves denote attracting and unstable equilibria, respectively; the inset shows their stability exchange at μ=0 . (B) After conflict 1 – 3 clears ( + ), the inherited state z+(0)=z†,− decomposes into a0+ϕmax+ along the updated dominant eigenvector and the perpendicular remainder y0+ . States evolve continuously as the dominant eigenvector rotates and the equilibrium amplitude decreases. Agent 3’s decision becomes positive; orders 1≺2 and 3≺2 permit agents 1 and 3 to progress concurrently. Pale elements show the previous configuration; the dashed 1 – 3 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, N∈{4,8,12,24,32} (minimum crossing angle αe=70∘ ). Points are means over n=50 scenarios for each method and population size; error bars are 95% bootstrap confidence intervals. (A) Safe-agent success is the percentage of agents reaching their goals without a safety violation. NDD maintains 100% success, whereas the success rate of LivePoint, the strongest baseline by this measure, remains below 100% 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 dsafe=0.7 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 1 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 2 s intervals, so closer spacing indicates slower motion. Crossed circles mark pairs whose separation fell below the dsafe=0.7 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 zi , measured speeds vi , 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 0.8 – 2.5 cm per robot produce traversal orders 2≺4≺6≺3≺1≺5 (A to C) and 6≺3≺4≺1≺5≺2 (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 vnom=0.2m/s . 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 α=1 and β2=−0.5 . The horizontal axis shows μ=λmax−λ∗ , the offset of the dominant eigenvalue of the interaction-sensitivity matrix A from the instability threshold λ∗ . The vertical axis shows a , the signed amplitude of the differentiated decision pattern along the dominant eigenvector ϕmax ; its equilibrium value a† appears in Equation ( 10 ). Solid blue and solid red denote stable ( ga<0 ) and unstable ( ga>0 ) equilibria, respectively, where ga:=∂g/∂a is evaluated at each equilibrium. (A) The positive-cubic model g=ητ+μa−0.5a2+a3−0.3a5 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 g=ητ+μa−0.5a2−a3 provides cubic saturation without a quintic term. Left column: With timing bias ητ=0 , the nonzero quadratic coefficient produces a transcritical exchange of stability at (μ,a)=(0,0) in both models. Right column: A positive timing bias ητ=0.05 unfolds the crossing, removes the equilibrium at a=0 , 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
i,j ; f,ℓ
Agent indices; instantaneous follower and leader, respectively, in an ordered interaction.
qi , vi
Agent i ’s position and velocity vector; vi is the scalar traversal speed.
zi , ui
Agent i ’s decision and attention states. Positive decisions favor speeding up; negative decisions favor slowing down.
vinom , vicmd
Agent i ’s nominal and commanded traversal speeds.
vi , vi
Lower and upper admissible traversal speeds of agent i ; vi bounds realized motion, including tracking and actuation transients.
x=(z,u,v)
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
Ni(t) , Ei(t)
Sensed neighbors and sensed directed interactions of agent i ; Ei={(i,j):j∈Ni} .
e=(i,j) , eˉ=(j,i)
Reciprocal directed interactions. Under the edge convention i→j , agent j ’s motion influences agent i ’s evidence.
P(t) , Econf(t)
Unordered physical-conflict pairs and their associated directed interactions. These exclude cleared pairs, even if still sensed.
G(t) , V(t)
Weighted directed physical-conflict graph and its agent set.
C(t) , Gc(t)
Index set of strongly connected components of the conflict graph and component c . Each component is a locally engaged group.
Vc , Pc
Agents and unordered physical-conflict pairs in group c .
Table S2 : Notation: interaction structure and conflict evidence.
Symbol
Definition
dsafe , Rsens
Required minimum spatial separation and sensing radius.
qce , αe
Projected crossing point and crossing angle.
rce
Half-length of a contested segment, dsafe/sinαe .
dcae , tcae
Projected closest-approach distance and time.
dprox , tprox
Spatial and temporal proximity buffers in the pressure map.
dk−e
Agent k ’s remaining distance to its contested-segment entry boundary.
Table S3 : Notation: conflict geometry, timing, and safety.
Symbol
Definition
A
Sensitivity of conflict evidence to decision-induced speed changes at frozen conflict geometry and interaction topology; not a frozen interaction-weight matrix.
te,∗ , tˉ , tc
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.
λmax , ϕmax
Dominant eigenvalue of A and associated eigenvector defining the leading-order collective decision pattern.
λ∗
Spectral threshold for loss of stability of collective indecision.
μ=λmax−λ∗
Distance from the spectral threshold in the local critical equation.
a , x†
Critical-mode amplitude and differentiated equilibrium of the fast subsystem with state (z,u,v) .
Table S4 : Notation: spectral and bifurcation quantities.
Navigating safely through dense crowds requires collision avoidance that generalizes beyond the densities seen during training. Learning-based crowd navigation can break under out-of-distribution crowd sizes due to density-sensitive observation normalization and social-cost scaling, while analytical solvers often remain safe but freeze in tight interactions. We propose a reinforcement learning approach for dense, variable-density navigation that attains zero-shot density generalization using a density-invariant observation encoding with density-randomized training and physics-informed proxemic reward shaping with density-adaptive scaling. The encoding represents the distance-sorted K nearest pedestrians plus bounded crowd summaries, keeping input statistics stable as crowd size grows. Trained with N∈[11,16] pedestrians in a 3m×3m arena and evaluated up to N=21 pedestrians (1.3× denser), our policy reaches the goal in >99% of episodes and achieves 86% collision-free success in random crowds, with markedly less freezing than analytical methods and a >60-point collision-free margin over learning-based benchmark methods. Codes are available at https://github.com/jznmsl/PSS-Social.
We present DM3-Nav, a fully decentralized multi-agent semantic navigation system supporting multimodal open-vocabulary goal specification and multi-object missions. In our setting, decentralization implies operation without a central coordinator, global map aggregation, or shared global state at runtime. Robots operate autonomously and coordinate through ad-hoc pairwise communication, exchanging local maps, goal status, and navigation intent without synchronization. An implicit task allocation mechanism combining intent broadcasting and distance-weighted frontier selection reduces redundant exploration while preserving decentralized operation. Evaluations on HM3DSem scenes using the HM3Dv0.2 and GOAT-Bench datasets demonstrate that DM3-Nav matches or exceeds centralized and shared-map baselines while eliminating single points of failure inherent in centralized architectures. Finally, we validate our approach in a real-world office environment using two mobile robots, demonstrating successful deployment relying entirely on onboard sensing and computation. A video of our real-world experiments is available online: https://drive.google.com/file/d/1QiUSCn5rIvtuTUqtuXLPgmt6S8x9-MCZ/view?usp=drive_link
Safe and efficient robot navigation in crowds requires anticipating pedestrian motion despite uncertain and potentially shifting prediction errors. Existing reactive methods can produce oscillatory behavior, while predictive planners often treat forecasts as exact or rely on restrictive error models. Incorporating conservative uncertainty sets as hard constraints can also render model predictive control (MPC) infeasible. We propose CoCoNav, a crowd-navigation framework that combines online conformal calibration with runtime-certified planning. A horizon-specific conformal proportional--integral controller adapts trajectory-error bounds to regulate long-run empirical coverage, enabling the framework to respond to changing prediction errors. A relax-then-verify planner preserves solver feasibility by generating nominal trajectories with soft-constrained MPC and separately certifying them, together with contingency maneuvers, against the calibrated bounds before execution. Simulations and quadruped experiments show that CoCoNav achieves a favorable balance among collision avoidance, task success, and navigation efficiency relative to the evaluated baselines.
Cheng Guo, Mingzhe Ni, Zheng Liang +5
Department of Computer Science, The University of Manchester, Manchester, UK. · Human-Robot Interfaces and Interaction Laboratory, Italian Institute of Technology, Genoa, Italy. · Genisom AI, Shanghai, China. +3