Action-Consistent Decentralized Belief Space Planning with Inconsistent Beliefs and Limited Data Sharing: Framework and Simplification Algorithms with Formal Guarantees
Authors: Tanmoy Kundu, Moshe Rafaeli Shimron, Anton Gulyaev, Vadim Indelman
Organizations: Tanmoy Kundu is with the department of Computer Science and Engineering, IIIT-Delhi, India. · This work was carried out when he was with the department of Aerospace Engineering, Technion - Israel Institute of Technology, Haifa 32000, Israel. · Department of Computer Science and Engineering, IIIT-Delhi, New Delhi, Delhi 110020, India. · Moshe Rafaeli is with the Technion Autonomous Systems Program (TASP), Technion - Israel Institute of Technology, Haifa 32000, Israel. · Anton Gulyaev is with the department of Aerospace Engineering, Technion - Israel Institute of Technology, Haifa 32000, Israel. · Vadim Indelman is with the department of Aerospace Engineering and with the department of Data and Decision Sciences, Technion - Israel Institute of Technology, Haifa 32000, Israel.
In multi-robot systems, ensuring safe and reliable decision making under uncertain conditions demands robust multi-robot belief space planning (MR-BSP) algorithms. While planning with multiple robots, each robot maintains a belief over the state of the environment and reasons how the belief would evolve in the future for different possible actions. However, existing MR-BSP works have a common assumption that the beliefs of different robots are same at planning time. Such an assumption is often unrealistic as it requires prohibitively extensive and frequent data sharing capabilities. In practice, robots may have limited communication capabilities, and consequently beliefs of the robots can be different. Crucially, when the robots have inconsistent beliefs, the existing approaches could result in lack of coordination between the robots and may lead to unsafe decisions. In this paper, we present decentralized MR-BSP algorithms, with performance guarantees, for tackling this crucial gap. Our algorithms leverage the notion of action preferences. The base algorithm VerifyAC guarantees a consistent joint action selection by the cooperative robots via a three-step verification. When the verification succeeds, VerifyAC finds a consistent joint action without triggering a communication; otherwise it triggers a communication. We design an extended algorithm R-VerifyAC for further reducing the number of communications, by relaxing the criteria of action consistency. Another extension R-VerifyAC-simp builds on verifying a partial set of observations and improves the computation time significantly. The theoretical performance guarantees are corroborated with simulation results in discrete setting. Furthermore, we formulate our approaches for continuous and high-dimensional state and observation spaces, and provide experimental results for active multi-robot visual SLAM with real robots.
Figures & tables
Figure 1: (a) Two robots, r and r′ , acquire separate observations ( zr,zr′ ) and begin a planning session. The robots aim to cooperatively reach the green star while satisfying a safety property of avoiding obstacles and collisions; each agent has two candidate actions \bigl(\{a^{r},\bar{a}^{r}\}\text{ for robot r, and }\{a^{r^{\prime}},\bar{a}^{r^{\prime}}\}\text{ for robot r^{\prime} }\bigr) . (b) The robots communicate their observations to each other (red color), after which their histories, and beliefs, become consistent. Decentralized MR-BSP in such a case yields the same best joint action for both robots. Here, Hc represents the common history between the robots prior to acquiring the observations zr and zr′ . (c) The robots do not communicate their observations, and as a result, the robots’ beliefs become inconsistent. This causes the robots to conclude inconsistent joint-actions, which leads to a collision.
Figure 2: Illustration of the objective function J(b,aˉ) as a belief- and action-dependent surface. Fixing a belief b selects a slice, or profile, J(b,⋅) . The figure shows several such slices for different beliefs bk(i) . Each slice has a corresponding optimal joint action aˉ⋆(bk(i))∈argmaxaˉ∈AJ(bk(i),aˉ) .
Figure 3: Consider two robots r and r′ . The robots have different beliefs br and br′ , respectively. Plots of J(b,a) -values for different joint actions ( a1 - a5 ) is shown for robot r (red) and r′ (blue). Though the robots compute different rankings of the actions a1 , a3 , a4 and a5 , the rank of action a2 is consistent (rank-1) for both the robots. The rank refers to the order of preference of the actions irrespective of the J -values of the actions. So, in this case action consistency is satisfied, and both the robots select the joint action a2 .
Figure 4: Illustration of Hr,Hr′,HcHr,r′,ΔHr,r′ , and ΔHr′,r . See text for details.
Figure 5: Illustration of VerifyAC from the perspective of robot r . Robots r and r′ have inconsistent beliefs bkr and bkr′ at time k . Candidate joint actions are aˉ and aˉ′ . Triangles and squares denote objective function ( J(.) ) evaluations for r and r′ respectively. (a) Step 1 of r : Robot r computes its belief for its actual observation. Chooses aˉ as the best action. (b) Step 1-2 of r : In Step 2, r computes J(.) for each possible observation of r′ . All the observations are consistent in favor of aˉ . (c) Step 1-2 of r′ : Similarly, robot r′ computes Step 1 for its actual observation, and Step 2 for all possible observations of r . (d) Step 3 of r : Combines (a)-(c) and verifies that the observations at each step are consistent in favor of action aˉ . Hence, r can be assured that r′ also has chosen aˉ . Thus r chooses action aˉ at time k .
Figure 6: Flowchart of EnforceAC and the conditions for communications.
Figure 7: Illustration of R-VerifyAC from the perspective of robot r . Consider, robot r selects action aˉ in step 1. Even though all the observations are not in favor of aˉ , R-VerifyAC provides (a) probabilistic guarantee on MR-AC, or (b) a comm is triggered from r to r′ . Triangles and squares represent the J -values corresponding to the observations in steps 2 and 3 respectively. Let, 1−ϵ=0.1 . (a) For action aˉ , in step 2, Claˉ2Claˉ=Cl∗2Cl∗=0.3+0.5=0.8>1−ϵ ; in step 3, Claˉ3Claˉ=0.4+0.3=0.7>1−ϵ . So, according to Definition 5.2 , ϵ\textsc−MRACr=true , and according to Theorem 5.4 , robot r will not trigger a comm . Probability of MR-AC with both robots choosing aˉ is Claˉ2Claˉ=0.8 ; probability of robot r choosing aˉ but r′ choosing an inconsistent action a ( =aˉ ) is 0.2 ; and probability of r′ triggering a comm is 1−0.8−0.2=0 . (b) For action aˉ , in step 2, Claˉ2Claˉ=0.2+0.2=0.4<1−ϵ and Claˉ2Claˉ=Cl∗2Cl∗ . So, according to Definition 5.2 , ϵ\textsc−MRACr=false , and according to Theorem 5.4 , robot r will trigger a comm from itself to r′ .
Figure 8: Flowchart of guarantees provided by EnforceAC that calls R-VerifyAC .
Figure 9: Illustration of Adaptive-Bounds in steps 2 and 3 of R-VerifyAC-simp . From the perspective of robot r , the figures are shown for step 3. Dashed line represents the threshold ( 1−ϵ ). Upper (ub) and lower bounds (lb) of Cl(.) are shown. (a) After iteration i , the bounds of different actions are overlapping, thus making it difficult to choose a particular action. (b) Up to iteration i+j , Adaptive-Bounds iteratively adds new observations in the reduced set of observations. Case-1: Action aˉ is chosen in step 1. Action aˉ has higher lb(.) than the ub(.) of any other action. So, aˉ can be chosen in Step 3 using deterministic bounds. Case-2: Action aˉ′ is chosen in step 1. comm is self-triggered by robot r as lb(.) of aˉ′ is below the threshold. Case-3: Action aˉ′′ is chosen in step 1. lb(.) of aˉ′′ is higher than the threshold, however aˉ′′ is not the rank-1 action with highest Cl(.) value. Probabilistic guarantee can be provided in favor of aˉ′′ .
Figure 10: Belief-dependent objective profiles for robots r (left) and r′ (right). Initially, incompatible local maximizers result in the executed joint action aˉ4 which is suboptimal under both beliefs br,(0)k and br′,(0)k (first row); after n data sharing iterations, robots r and r′ have access to updated beliefs bkr,(n) and bkr′,(n) . The corresponding distinct objective profiles may have a common maximizer aˉ2 (second row), a situation that our approach identifies with deterministic or probabilistic guarantees. Full data sharing yields identical beliefs ( bkr,F and bkr′,F ) and objective profiles (third row). See Section 6 for details.
Figure 11: Illustration of the bounds of the cumulative likelihoods of different actions, according to δ0 which is calculated according to a pre-defined α0 and number of samples in the estimators N . Figure 11(a) shows overlapping bounds between different actions for a pre-defined confidence level α0 and the number of samples N . To tighten the bounds, more samples are added to the estimators, which changes the value of the estimators a little, but also decreases δ0 . Figure 11(b) shows the resulting bounds after increasing the number of samples, where the bounds are tighter and do not overlap.
Max-Entropy
Prior-Knowledge
Random
Algorithm
Initialization
Initialization
Initialization
Baseline-I
1.2 ± 0.06 sec
1.3 ± 0.06 sec
1.4 ± 0.14 sec
Baseline-II
1.3 ± 0.07 sec
1.2 ± 0.07 sec
1.3 ± 0.07 sec
EnforceAC
17.8 ± 0.70s sec
13.1 ± 2.24 sec
13.4 ± 0.20 sec
R-EnforceAC
ϵ=0.3
23.1 ± 0.85s sec
18.1 ± 0.26 sec
15.5 ± 0.42 sec
Table 1: Search and Rescue simulation runtime statistics.
Action Inconsistencies
Algorithm
Max-Entropy -Init
Prior-Knowledge -Init
Random -Init
Max-Entropy -Init comm-restric=20
Max-Entropy -Init comm-restric=30
Baseline I
0 (0.0%)
0 (0.0%)
0 (0.0%)
14 ± 2 (7.0 ± 1.0%)
21 ± 3 (10.5 ± 1.5%)
Baseline II
179 ± 6 (89.5 ± 3.0%)
180 ± 5 (90.0 ± 2.5%)
173 ± 6 (86.5 ± 3.0%)
179 ± 6 (89.5 ± 3.0%)
179 ± 6 (89.5 ± 3.0%)
EnforceAC
0 (0.0%)
0 (0.0%)
0 (0.0%)
–
16 ± 7 (8.0 ± 3.5%)
R-EnforceAC (ϵ=0.3)
0 (0.0%)
0 (0.0%)
0 (0.0%)
14 ± 1 (7.0 ± 0.5%)
21 ± 2 (10.5 ± 1.0%)
R-EnforceAC (ϵ=0.7)
0 (0.0%)
1 ± 1 (0.5 ± 0.5%)
1 ± 1 (0.5 ± 0.5%)
14 ± 1 (7.0 ± 0.5%)
21 ± 2 (10.5 ± 1.0%)
Table 2: Search and Rescue simulation Action Inconsistency and Communications.
Figure 12: Results from a specific seed run of simulations of different algorithms with Prior-Knowledge initialization and zero communication restrictions, running for E=200 time steps. (a) Comparison of the return values over time for different algorithms. (b) Comparison of the number of time steps since last communication ( p -values) over time for different algorithms.
Figure 13: Action Consistency Probability Guarantees over time of robot r running R-EnforceAC with Prior-Knowledge initialization and zero communication restrictions for E=200 time steps, with (a) ϵ=0.7 and (b) ϵ=0.9 . The green bars indicate the action selection was consistent between the robots, and the red bars indicate the action selection was inconsistent.
Figure 14: The DJI Robomaster, equipped with cameras and LiDAR sensors.
Figure 15: SuperGlue feature matching for a pair of consecutive images.
Figure 16: Estimated trajectories and landmarks in the local belief maintained by robot r 16(a) and by robot r′ 16(b) , immediately after the final data-sharing iteration of the planning process based on R-VerifyAC and before motion execution. Gray edges show visual observations. Blue ellipses denote uncertainty around the current robot poses based on the locally available belief of each robot.
Figure 17: Candidate relative-pose sequences applied to prior belief bkr . Labels ξ^kr and ξ^kr′ mark estimated current poses. Each robot has two candidate action sequences, with corresponding predicted trajectories. The trajectories are shown in blue shades for r and brown for r′ . Pale green shows prior trajectories and motion factors. Gray shows predicted visual observations; prior-belief visual observations remain hidden.
Figure 18: Plots from the perspective of robot r′ : (a) data-sharing iteration 1, (b) data-sharing iteration 2. (top) Objective values ( J ) for different joint robot actions at step 2 of R-VerifyAC. Each color corresponds to a different sampled realization of missing measurements. In this scenario, ten samples of missing observations are generated. (bottom) Estimated cumulative likelihood ( 43 ) of each action. Due to additional data shared between robots, the distribution of objective values in (b) differs from (a) .
Figure 19: Sampled visual landmark observations of robot r at data-sharing iteration 1, as obtained from the belief maintained by robot r′ during Step 2 of R-VerifyAC. These sampled observations are denoted with dashed blue edges. Solid gray edges denote visual observations available to robot r′ , including local observations and those received from robot r . Each plot corresponds to another prior belief. Panels (a), (b), and (c) show samples 0, 1, and 2 from Figure 18(a) , respectively.
Real-world robots often operate in settings where objective priorities depend on the underlying context of operation. When the underlying context is unknown apriori, multiple robots may have to coordinate to gather informative observations to infer the context, since acting based on an incorrect context can lead to misaligned and unsafe behavior. Once the underlying true context is inferred, the robots optimize their task-specific objectives in the preference order induced by the context. We formalize this problem as a Multi-Robot Context-Uncertain Stochastic Shortest Path (MR-CUSSP), which captures context-relevant information at landmark states through joint observations. Our two-stage solution approach is composed of: (1) CIMOP (Coordinated Inference for Multi-Objective Planning) to compute plans that guide robots toward informative landmarks to efficiently infer the true context, and (2) LCBS (Lexicographic Conflict-Based Search) for collision-free multi-robot path planning with lexicographic objective preferences, induced by the context. We evaluate the algorithms using three simulated domains and demonstrate its practical applicability using five mobile robots in the salp domain setup.
Collaborative Robotics and Intelligent Systems (CoRIS) Institute, Oregon State University, Corvallis, OR 97331, USA · Khoury College of Computer Sciences, Northeastern University, Boston, MA 02115, USA
Decentralized multi-robot motion planning requires each robot to generate collision-free trajectories from local observations, without global sensing or reliable communication. However, most existing planners, whether classical or learning-based, generate trajectories from a static snapshot of the local observation, which limits their ability to anticipate the future behavior of neighboring robots. This limitation is critical as the number of robots increases and the environment becomes more cluttered. Motivated by world models that use future state estimation to improve planning decisions, this paper introduces Simulation-Informed Diffusion (SID), a decentralized framework built on constraint-aware diffusion models (CADM) that simulate neighboring robots' future trajectories to guide each robot's own planning. SID first uses CADM to simulate the future trajectories of neighboring robots from their currently observed states, and then uses the same CADM to plan each robot's own trajectory under safety constraints informed by these simulations. Crucially, the accurate simulation of neighbors enables a minimal communication scheme that triggers coordination only when necessary in highly congested scenarios. Experiments across diverse environments show that SID consistently outperforms baseline methods in terms of planning effectiveness and constraint satisfaction, and scales to scenarios with 108 robots and 160 obstacles.
Jinhao Liang, Sven Koenig, Ferdinando Fioretto
University of Virginia · University of California, Irvine
Multi-robot systems (MRS) offer significant advantages over single-robot platforms by enabling information sharing and coordination for different tasks in complex environments. However, reliable cooperation critically depends on inferring trust over both information sources and their reported hypotheses, particularly under partial observability and potential adversarial interference. Existing approaches frequently depend on pre-established trust relationships or side-channel information, which may not be available or reliable in realistic MRS deployments. This work introduces NeST-Bayes, a neural-symbolic framework that jointly infers robot and hypothesis trust using only inter-robot observation consistency, without requiring preassigned robot trust, reputation information, or side-channel identity signals. NeST-Bayes infers instantaneous trust evidence scores for robots and object hypotheses by reasoning over ego-centric relational graphs constructed from cross-robot observation consistency. These evidence scores are accumulated over time through Bayesian updates of Beta-distributed trust beliefs to maintain temporally consistent trust estimates. Extensive evaluations show that NeST-Bayes achieves the highest mean object precision and robot recall across all benchmark settings, and the highest robot precision and object recall in most settings, compared to trust-based methods. Under aggressive optimized attacks, it achieves 98.8% robot precision with 93.8% recall and 98.3% object precision with 95.4% recall. In an occlusion-rich Webots warehouse, it maintains 92.5% robot precision with 92.0% recall and 97.3% object precision with 85.0% recall. These results demonstrate joint improvements in the reliability and coverage of retained information.