{"id":"e510f78d-62ad-442e-8b3e-983d1b538487","arxiv_id":"2607.20772","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":8,"one_line_summary":"A decoupled planner first biases each robot's global path toward social conventions and shared routes, then solves a small mixed-integer program over encounter windows to produce scalable, conflict-free fleet trajectories.","lead":"This paper proposes a robot navigation system that adds social rules like keeping right into the long-range path planner, then uses a shared 'social graph' of common routes and a mixed-integer optimization step to make fleets avoid collisions. The pitch: making all robots follow the same social conventions shrinks the set of possible conflicts, so multi-robot coordination becomes a small, fast optimization problem.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Collision-free guarantee rests on unquantified constant-velocity and delta=1s assumption; no bound on tracking/delay errors, so the central claim is not fully established.","rationale":"The reader's weakest assumption correctly identifies the unquantified constant-velocity and delta safety margin as the key threat to the conflict-free claim. I agree because the proof of safety in the MICP is purely combinatorial: it ensures temporal ordering at event waypoints under the assumption of exact piecewise-constant-velocity execution. Real robots accelerate, localize with error, and experience actuation noise; without a bound on these deviations, the schedule can fail in a way that is not captured by the model. This is not a disagreement with the overall architecture, which has independent support from the simulation and hardware demonstrations, but it does mean the strongest claim--'conflict-free trajectories'--is conditional on an unverified margin. Other issues, such as the A* optimality claim with potentially negative edge costs in Eq. (2)-(3), are real but less central to the coordination contribution. I therefore do not move the reader's CONDITIONAL verdict; no change is needed beyond what the reader already requested.","tokens_in":17853,"tokens_out":14793,"duration_ms":132923,"concrete_test":"In the Environment 1 four-robot scenario (Fig. 9), replace ideal constant-velocity execution with a trapezoidal acceleration profile (e.g., a_max=1 m/s^2) and add bounded tracking noise (e.g., +/-0.1 m/s speed error, +/-0.15 m localization error). Sweep delta from 0.2 s to 2.0 s and measure the minimum inter-robot distance over trials. Determine the smallest delta that keeps clearance above the robot diameter; if it exceeds the reported delta=1 s, the Section 3.3.3 safety claim is unsupported and delta must be re-derived from control/estimation error bounds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that the MICP produces conflict-free trajectories (Section 3.3.3) depends on the assumption that robots move at constant velocity between event waypoints and that the hand-set safety margin delta=1s absorbs all localization, actuation, and tracking error (Sections 3.3.1, 5.4). The paper never derives how large a deviation from the scheduled piecewise-constant velocity profile can be tolerated before constraints (6)-(7) are violated. If a robot is delayed by more than delta at an event waypoint, the Big-M ordering constraints can be violated; if a robot drifts laterally, the encounter windows computed from nominal paths no longer describe the actual conflict set. Section 5.4 acknowledges this by falling back to sequential/unified replanning, but that means 'conflict-free' is a property of the nominal schedule, not of executed motion. Because conflict-free coordination is the headline contribution, this unquantified safety margin is the most load-bearing weak point.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a decoupled multi-robot navigation framework. A modified A* planner embeds macroscopic social norms (right-wall adherence, path constancy, and a buffer from the left wall) into the edge cost. Planned paths are shared to build a social graph that biases future planning, improving path consistency and reducing planning time. The structured paths are then used to formulate a mixed-integer convex program (MICP) over sparse event waypoints and encounter windows, producing conflict-free arrival times for intersection, opposite-direction, and same-direction encounters. The approach is evaluated in three simulated environments and on physical differential-drive robots in a building hallway and intersection scenarios, with comparisons to CBS and prioritized planning for coordination and to A*/RRT* for path planning.","tokens_in":18105,"tokens_out":5690,"duration_ms":51018,"significance":"If the framework performs as claimed, the contribution is a practical decomposition of social multi-robot navigation: global social path planning reduces the conflict space, and sparse event-waypoint scheduling allows coordination of large fleets with modest solve times. Strengths include the release of code and videos, a hardware demonstration, a distributed constraint-generation protocol, and an explicit taxonomy of encounter types. However, the validation and safety guarantees are not yet at the level needed to support the central claims: the social-compliance metric is optimized by construction, the A* optimality argument is not valid for the stated cost, and the conflict-free guarantee is conditional on unquantified execution assumptions.","major_comments":[{"comment":"The claim that the Manhattan heuristic is 'consistent and admissible, guaranteeing that A* finds the lowest cost path' is unjustified because C_const = d_right(x)-d_right(x') can be negative. The edge cost c(x',x) can therefore be less than the Euclidean distance and can even be negative. With negative edge costs, the Manhattan distance is not a lower bound on the remaining cost, and A*'s optimality guarantee does not hold. The authors should either restrict the social cost weights/domain so that c(x',x) >= ||x-x'||_2, or derive a valid admissible heuristic for the modified cost and state the resulting optimality guarantee.","section":"3.2.1, Eqs. (2)-(3)"},{"comment":"The headline metric 'mean right distance' is exactly the term C_right minimized in Eq. (3). The improvement shown in Table 2 (e.g., 8.31 vs 2.64 in Environment 1) is therefore an expected consequence of optimizing the same quantity, not an independent measure of social compliance. This circularity does not validate that the paths are socially acceptable to humans. The authors should validate with independent metrics (e.g., human trajectory data, proxemics studies, or a held-out social cost) or explicitly reframe Table 2 as a sanity check of the optimizer rather than as evidence of social compliance.","section":"4.1, Table 2"},{"comment":"The conflict-free claim is nominal: it holds only under the constant-velocity interpolation between event waypoints and assumes that the hand-set margin delta=1s absorbs all localization, actuation, and tracking error. No bound is derived for how large a delay or lateral drift can be before constraints (6)-(7) are violated. Section 5.4 acknowledges the fallback to sequential/unified replanning, but this means 'conflict-free trajectories' is not guaranteed for executed motion. Please quantify the allowable deviations or explicitly scope the claim to the nominal schedule rather than the executed motion.","section":"3.3.1 and 5.4, Eqs. (6)-(7)"},{"comment":"The dynamic Big-M constant M = 2 * sum_{r} sum_k l_k^r / Vmax^r is not obviously a valid upper bound on arrival-time differences in all feasible schedules. If M is too small, an inactive disjunctive constraint in (6)-(7) can become active and cut off the true optimum, compromising the MICP's correctness. A proof that M is a horizon bound under the SOC objective, or a more conservative choice of M, is required.","section":"3.3.2, Eq. (8)"}],"minor_comments":[{"comment":"C_const = d_right(x) - d_right(x') is signed; the text says it 'penalizes changes' but a negative value would reward moving away from the right wall. Consider using an absolute value or explicitly explaining the intended asymmetry.","section":"3.2.1, Eq. (3)"},{"comment":"CBS and PP are run on a 4x-downsampled map while the proposed method uses the full-resolution map. This discrepancy should be discussed when comparing solve times and success rates, as it affects the fairness of the comparison.","section":"4.3.2"},{"comment":"The social planner computation times (20-57 s) are large. Section 4.2 shows that the social graph reduces planning time, but it would be helpful to report end-to-end times that include graph construction and planning with the biased cost.","section":"Table 2"},{"comment":"The figures would be clearer with time-stamped trajectory overlays or explicit reference to the videos in the repository, so that the collision-free behavior can be verified.","section":"Figures 14, 15"},{"comment":"Several references are dated 2025-2026 (e.g., [17], [18], [23]). Please verify all citations are to published or otherwise available works.","section":"References"},{"comment":"The acronym SOC is used for 'sum of completion' times; please spell it out at first use to avoid ambiguity with other common meanings.","section":"3.3.3"}],"recommendation":"major_revision","confidential_remarks":"The framework is interesting and the hardware demonstration is a strong element, but the paper currently overstates its guarantees relative to the evidence. The most serious issues are the unvalidated safety margin for the conflict-free claim and the circular social-compliance metric; the A* optimality issue is also load-bearing and needs a fix. The paper is within the journal's scope and could become suitable after these points are addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper is a genuinely integrated framework, not just a bag of tricks. The new thing is the combination: a modified A* with social costs, a heatmap-based social graph built from broadcast paths, and an MICP that coordinates arrival times at sparse encounter windows. It is well written and the hardware demo plus public code give real evidence the pipeline runs. The claim that social consistency shrinks the coordination problem is plausible and the experiments show lower overlap counts and faster MICP solve times than CBS/PP baselines.\n\nWhat's good: the decoupling is clean. The event-waypoint formulation makes the integer complexity scale with encounter windows, not path resolution. The social graph concept is intuitive and the temporary-obstacle handling shows thought. The code and videos are a plus.\n\nSoft spots, in order. First, the A* optimality claim in Section 3.2.1 is not right as stated: Eq. 3 includes C_const which can be negative, so edge costs can be negative, and the Manhattan heuristic is not necessarily admissible for the total cost. The planner probably still works fine for finding reasonable paths, but the 'optimality' sentence should be fixed or softened. Second, the main compliance metric—mean distance to the right wall—is essentially the objective term C_right, so Table 2's compliance improvement is partly by construction. That doesn't destroy the coordination results, but you can't cite those numbers as independent validation. Third, the collision-free guarantee is nominal: it relies on constant velocity between event waypoints plus a hand-set delta=1s to absorb tracking and localization error, and no bound is given for how large deviations can be before constraints (6)-(7) break. The paper acknowledges the fallback to replanning, which is honest, but the headline claim should be stated as 'conflict-free under the constant-velocity schedule,' not as executed safety. Finally, the social graph thresholds (heatmap threshold, minimum component size) are not reported, and the CBS/PP baselines use a downsampled map, so the comparison is not apples-to-apples.\n\nNone of these are fatal. The architecture is defensible and the experiments demonstrate the system working. The paper deserves serious peer review; an editor should send it out. If I were reviewer, I'd ask for a revised statement on A* optimality (or drop it), explicit social graph parameters, and a clearer discussion of what delta does and doesn't guarantee.\n\nWho it's for: people working on practical multi-robot navigation in human spaces, especially those combining global social planning with trajectory optimization. I'd bring it to reading group and would cite it if I was working in that area.","headline":"A well-integrated systems framework that mostly delivers on its promise; the main caveats are a flawed A* optimality claim and an unquantified safety margin.","tokens_in":18568,"tokens_out":3117,"would_cite":true,"duration_ms":25201,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Encoding social conventions into global path planning reduces multi-robot collision avoidance to a small mixed-integer convex program whose cost grows with the number of encounter windows, not path resolution.","keywords":["social navigation","multi-robot coordination","path planning","social graph","mixed-integer convex programming","A* algorithm","trajectory coordination","human-centric environments"],"falsifier":"Deliberately delay one robot by δ+0.5 seconds (or let its actual velocity deviate 20% from the interpolated constant between event waypoints) in simulation without replanning, and sample the minimum inter-robot distance; if it ever falls below the robot diameter, the constant-velocity-plus-δ assumption that underwrites the conflict-free guarantee is violated.","tokens_in":17717,"feed_emoji":"🤖","tokens_out":4476,"duration_ms":39749,"temperature":0.7,"pith_summary":"This paper argues that enforcing social conventions at the global path-planning stage — keeping right, avoiding weaving, leaving buffer room — turns the hard problem of coordinating a fleet of mobile robots into a small, fast optimization. The authors embed these norms into an A* cost function and have robots share their planned paths to build a 'social graph' of established routes, which makes future paths consistent and cheap to compute. Because socially consistent paths overlap only at predictable places — intersections, opposite-direction hallways, and same-direction lanes — the fleet's collision-avoidance constraints collapse to a set of 'encounter windows,' and a mixed-integer convex program assigns arrival times at these windows. The result is conflict-free trajectories whose solve time grows with the number of encounters, not path resolution, and the same formulation handles simultaneous, sequential, or partially fixed fleet planning. If the argument holds, social norms are not an extra burden on multi-robot navigation but a simplification that makes it scalable.","feed_headline":"Social paths shrink robot traffic to a few conflict windows","feed_subtitle":"Keep-right planning plus a shared route graph lets a convex program schedule collision-free fleets in about a second.","key_machinery":"The social graph: a directed subgraph built from directional heatmaps of previously planned paths, which biases future A* plans onto established lanes (via a small epsilon penalty for off-graph edges) and thereby concentrates potential conflicts at a few locations. On top of it, the mixed-integer convex program (MICP) defines event waypoints at the entry/exit of each 'encounter window' — the merged contiguous conflict segment between two robots — and uses Big-M disjunctive constraints with one binary variable per window to order robots through intersections and opposite-direction corridors, or to enforce leader-follower ordering in same-direction windows. The machinery works because the numb","core_discovery":"The central claim is that social conventions, far from complicating multi-robot navigation, reduce the space of possible robot-robot conflicts to a few discrete scenarios. With a keep-right cost function and a shared social graph of established lanes, overlapping paths concentrate at intersections, opposing-direction corridors, and same-direction routes. The paper encodes each overlap as an 'encounter window' with a single integer choice — who goes first, or who leads — and solves the resulting mixed-integer convex program over event-waypoint arrival times. The optimization is linear, uses one binary variable per encounter, and recovers full trajectories by constant-velocity interpolation be","pith_inferences":["Because the social cost is pluggable, the same decoupled architecture should transfer to left-hand-traffic or other cultural norms by swapping the cost terms; the encounter-window taxonomy would still apply.","The paper leaves safety margin δ hand-set; a natural extension is to bound the deviation from constant velocity and certify a δ that guarantees separation, rather than relying on replanning when the margin is exceeded.","The event-waypoint idea could be extended to moving humans by treating them as short-horizon 'robots' with uncertain windows, turning the MICP into a stochastic or robust formulation.","Learning the social graph from human trajectories instead of engineered costs is the paper's suggested next step; a concrete test is whether graph convergence time and path consistency change materially when costs are learned."],"forward_implications":["Robots that keep to a shared set of lanes overlap almost only at intersections and shared-direction pipes, so collision checks concentrate where conflicts are actually possible.","The trajectory coordinator's solve time stays near one second in simulations with growing fleet size, while centralized baselines time out at 120 seconds.","One MICP formulation covers dispatching a new robot into an active fleet, dispatching a whole fleet at once, or planning a subset around already-committed robots — only which variables are free changes.","Distributed constraint generation makes the collision-checking phase scale roughly linearly with robot count instead of quadratically.","In hardware experiments, head-on hallway traffic needs no coordination at all once social paths are used, because keep-right already separates the robots."],"fun_headline_variants":["Social norms cut multi-robot conflicts to single-choice windows","Keep-right planning eases coordination to one integer per encounter","Social paths turn multi-robot coordination into a convex program","Shared route graph lets convex solver schedule fleets in seconds","Decoupled planning plus social norms makes navigation predictable"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"Between the sparse event waypoints each robot is assumed to move at constant velocity, and the fixed one-second time margin is relied on to absorb every localization, actuation, and tracking error; no bound is given for how large a deviation can be before the computed 'conflict-free' trajectories stop being safe.","fun_headline_variants_meta":{"raw":{"variants":["Social norms cut multi-robot conflicts to single-choice windows","Keep-right planning eases coordination to one integer per encounter","Social paths turn multi-robot coordination into a convex program","Shared route graph lets convex solver schedule fleets in seconds","Decoupled planning plus social norms makes navigation predictable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000348,"raw_usage":{"total_tokens":1736,"prompt_tokens":734,"completion_tokens":1002,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":478,"completion_tokens_details":{"reasoning_tokens":923}},"tokens_in":478,"tokens_out":1002,"duration_ms":8834,"temperature":1.0,"reasoning_tokens":923,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T09:24:39.357698+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Deliberately delay one robot by δ+0.5 seconds (or let its actual velocity deviate 20% from the interpolated constant between event waypoints) in simulation without replanning, and sample the minimum inter-robot distance; if it ever falls below the robot diameter, the constant-velocity-plus-δ assumption that underwrites the conflict-free guarantee is violated.","supporting_citations":[],"review_version":1}