PaperlayerView exact revision on arXiv

Source-linked AI summary

Hierarchical Building-Floo-Room Framework for Privacy-Preserving Autonomous Delivery in Large-Scale Buildings

Xu Xiaoji, Luo Rui, Chen Jinhua, Xiang Changying, Zhang Leihan, Liao Zhongyuan

arXiv:2610.21361v1cs.RO

TL;DR

Large-scale building delivery requires coordination across building, floor, and room levels, while current approaches may overlook hierarchical structure and privacy constraints. This paper proposes a hierarchical CVRP framework integrated with robotic mapping and navigation. Its conclusion reports reliable real-world multi-building and multi-floor performance, while identifying theoretical bounds, cooperative optimization, and uncertainty-aware planning as future work.

  • Problem

    Building delivery requires coordination across multiple spatial levels, while existing approaches may omit hierarchical structures and room-level privacy constraints.

    Source: §1 · pp. 1–2

  • Method

    The paper decomposes routing with a Building–Floor–Room hierarchical formulation and integrates planning with mapping, localization, and navigation on a delivery robot.

    Source: §7 · pp. 31–32

  • Results

    Multi-building and multi-floor experiments report that the framework's algorithmic advantages translate into reliable real-world performance.

    Source: §7 · p. 32

  • Takeaways & Limitations

    The integrated system connects hierarchical optimization with physical delivery execution using reachability-aware distances and a non-interactive, privacy-preserving robot design.

    Source: §7 · p. 32

    Future work includes theoretical performance bounds, multi-robot cooperative optimization, and uncertainty-aware planning under dynamic demand and access constraints.

    Source: §7 · p. 32

Abstract

from arXiv · show

Autonomous delivery in large scale buildings requires coordinated planning across multiple spatial levels, including building, floor, and room, while ensuring scheduling efficiency. Existing methods often focus solely on algorithmic development, neglecting integration with physical robotic platforms, and rarely validate performance in real world scenarios. Many approaches also overlook hierarchical building structures and room level privacy constraints, limiting practical applicability. To address these challenges, this paper presents a hierarchical delivery framework based on a Building-Floor-Room abstraction, which decomposes the problem across multiple levels to significantly reduce optimization complexity. We formulate a building aware extension of the capacitated vehicle routing problem (CVRP) that explicitly models inter building and inter floor connectivity, room level access constraints, and privacy sensitive areas, enabling globally feasible and privacy compliant task assignment and routing. Based on this hierarchical model, the framework can evaluate delivery efficiency across different building layouts and optimize depot placement for specific configurations. At the execution level, we introduce a novel hardware design for non interactive, privacy preserving delivery, supported by reachability aware distances and a closed loop mapping, localization, and navigation system, ensuring consistency between planned routes and physical navigation. The proposed framework is validated on a real multi sensor robotic platform, demonstrating reliable multi floor delivery with improved path rationality and overall efficiency.

1. Introduction

Large-scale delivery must coordinate routing across buildings, floors, and rooms, where connectivity, elevator transfers, privacy constraints, and execution uncertainty challenge conventional routing. The paper addresses these issues with hierarchical, privacy-aware planning, integrated robotic execution, and layout and depot evaluation.

Problem setting

  • Building, floor, and room levels pose distinct routing challenges: costly sparse inter-building links, elevator transfer costs and waits, and complex room layouts with privacy-restricted zones.These features complicate scheduling and local reachability.Source: §1 · p. 2
  • Classical VRP assumptions about Euclidean distances and metric properties fail in these settings, while a unified graph across all levels increases complexity and impedes real-time planning.The passage characterizes the resulting state-space growth as a combinatorial explosion.Source: §1 · p. 2

Contributions

  • The paper introduces a Building–Floor–Room model and building-aware CVRP that account for inter-building and inter-floor connectivity, room access, and privacy-sensitive areas.The formulation is described as reducing optimization complexity while enabling globally feasible, privacy-compliant routing.Source: §1 · p. 3
  • The framework integrates mapping, localization, scheduling, and navigation with a non-interactive, privacy-preserving robot design to keep hierarchical plans consistent with physical execution.The introduction also proposes evaluating delivery efficiency across building layouts and optimizing depot placement for particular configurations.Source: §1 · pp. 2–3

2. Related Work

Prior work addresses hierarchical mapping, indoor routing constraints, and robust localization, but the paper identifies gaps in privacy-aware spatial models and closed-loop integration. It positions its framework as combining these concerns for delivery planning and execution.

2.1. Hierarchical and Semantic Environmental Modeling for Navigation

  • Hierarchical maps and graphs support reasoning across floors and spaces, but balancing geometric fidelity, semantic richness, and computational tractability remains an open problem.The review also notes that semantic mapping systems mainly target scene understanding or reconstruction, while few spatial models explicitly encode privacy constraints.Source: §2.1 · pp. 3–4

2. Related Work

  • The related-work review identifies the need for models that handle indoor non-Euclidean paths and asymmetric vertical-movement costs rather than standard metric assumptions.Standard VRP formulations are described as relying on symmetric and Euclidean distances that fail in structured indoor settings.Source: §2 · p. 3, §2.2 · p. 4

2.2. Vehicle Routing Problems with Indoor and Dynamic Constraints

  • Indoor VRP variants address timed deliveries, uncertainty, elevator waits, multi-floor scheduling, energy, and multiple robots, yet often lack SLAM-derived reachability and consistency information.The paper frames this omission as contributing to plan–execution mismatch across building levels.Source: §2.2 · p. 4

2.3. LiDAR SLAM, Fusion, and Closed-Loop System Integration

  • LiDAR, visual-inertial, and graph-based SLAM methods support state estimation and global consistency, but navigation modules often remain decoupled from high-level VRP scheduling.The proposed system feeds real-time spatial information into the hierarchical scheduler using Fast-LIO.Source: §2.3 · pp. 4–5

3. System Overview and Hierarchical CVRP Modeling

The framework combines mapping, reachability-aware cost construction, hierarchical task scheduling, subgoal decomposition, and feedback-based navigation. Its Building–Floor–Room representation supports a two-stage CVRP formulation with transformed demand data and stated operating assumptions.

3. System Overview and Hierarchical CVRP Modeling

  • The system links perception and mapping, reachable-distance construction, building-aware scheduling, subgoal decomposition, and local navigation with feedback.The overview describes feedback as supporting map refinement and dynamic re-dispatch.Source: §3 · p. 5, Figure 1 · p. 6

3.1. Hierarchical Building Representation

  • The environment is represented at building, floor, and room levels, with reachable building distances, elevator-transition costs, corridor graphs, and privacy penalties.The room-level graph includes corridor intersections, entrances, and task locations; its edges encode navigable corridors.Source: §3.1 · p. 5

3.2. Hierarchical Two-Stage Capacitated Vehicle Routing Formulation

  • A two-stage CVRP separates inter-building allocation from intra-building route optimization, enabling top-down task assignment and bottom-up route-cost refinement.The paper states that this decomposition keeps high-level scheduling consistent with detailed in-building navigation.Source: §3.2 · p. 7

3.2.1. Preprocessing and Data Transformation

  • Preprocessing splits buildings and demand nodes according to robot capacity and transforms in-building networks into complete graphs over demand nodes.For a demand of 15 and capacity Q = 4, the example creates four nodes with demands.Source: §3.2.1 · p. 8

3.2.2. Assumptions

  • The model assumes indivisible demand, homogeneous robots with sufficient daily range, capacity Q without daily parcel-weight constraints, and enough robots for feasible assignment.The text says the sufficient-robot assumption can be addressed in practice by assigning multiple trips to limited robots.Source: §3.2.2 · p. 8

3.2.3. CVRP Formulation

  • The CVRP uses binary variables to represent traversed inter-building and in-building arcs, with robot capacity Q and demand data defining the routing problem.The supplied formulation passages identify x_ij and y^k_ij as arc-traversal indicators.Source: §3.2.3 · p. 8, §3.2.1 · p. 8

Stage 1: Inter-Building CVRP.

The inter-building CVRP minimizes travel cost over duplicated building nodes and uses constraints to enforce route structure, flow balance, robot requirements, and capacity-feasible subtours.

Stage 1: Inter-Building CVRP.

  • The inter-building CVRP minimizes total travel cost over duplicated building nodes, arcs, and demands.The formulation includes flow-conservation and capacity constraints.Source: Stage 1: Inter-Building CVRP · p. 9
  • Constraints (9) and (10) give each building node exactly one outgoing and incoming arc, while constraint (11) balances flow at the depot.The passage also states that constraint (12) specifies the minimum robots required to serve all demands.Source: Stage 1: Inter-Building CVRP · p. 9
  • Constraint (13), a generalized subtour elimination constraint, eliminates subtours while enforcing capacity feasibility and can be implemented lazily to accelerate solving.Source: Stage 1: Inter-Building CVRP · p. 9

Stage 2: In-Building CVRP.

The section describes a two-stage CVRP that solves local routes within buildings after inter-building routing, then decomposes global routes into prioritized robot assignments and delivery sequences.

Stage 2: In-Building CVRP.

  • Each building assigned in Stage 1 receives an independent in-building CVRP; a constraint prevents multiple non-full-capacity tours within the same building.This preserves consistency with demand-duplication preprocessing.Source: Stage 2: In-Building CVRP · pp. 9–10

3.2.4. Validity and Complexity

  • Separability between inter-building and in-building routes supports decomposition, reducing the effective problem size to O(n^2) first-stage and O(m_i^2) second-stage binary variables.The exact worst-case complexity is not given in closed form, and ILP solvers may have rapidly growing search spaces.Source: §3.2.4 · p. 10

3.2.5. Algorithmic Procedure

  • The procedure preprocesses demands, solves the inter-building CVRP, solves each assigned building’s in-building CVRP independently, and maps the solutions to the original network.The algorithm returns the total delivery cost and delivery routes.Source: §3.2.5 · p. 10, Stage 2: In-Building CVRP · p. 10

3.3. Subgoal Decomposition

  • Because global routes specify locations but not execution order, subgoal decomposition assigns routes to robots by workload and capacity, then orders demands by priority.Higher-priority demands are dispatched earlier; parcel count, expedited status, and delivery urgency contribute to priority.Source: §3.3 · pp. 10–11

4. Unified Mapping and Autonomous Navigation System

The section presents a unified perception-to-control pipeline that connects hierarchical plans to physical navigation in multi-building, multi-floor environments. It combines a delivery robot design with calibrated sensing, mapping, odometry, and closed-loop planning and execution.

4. Unified Mapping and Autonomous Navigation System

  • The section frames the system as a unified perception–mapping–planning–control pipeline for executing planned routes and allocated demands in complex indoor environments.Its stated goal is reliable autonomous navigation across multi-building, multi-floor settings.Source: §4 · p. 11

4.1. Hardware Design

  • The robot integrates sensing, interaction, storage, and mobility modules, with four lockers for concurrent storage and delivery of up to four parcels.At the destination, an integrated planar push surface releases a parcel onto a desk or floor without direct user interaction; the contactless design avoids waiting for user arrival.Source: §4.1 · pp. 11–12

4.2. Sensor Fusion and Extrinsic Calibration

  • Joint extrinsic calibration establishes a geometrically consistent sensor-frame structure for downstream odometry, mapping, and navigation.The calibrated transforms express LiDAR points, IMU readings, and available wheel odometry in a common kinematic frame.Source: §4.2 · p. 13

4.3. Tightly Coupled Odometry and 3D Mapping

  • Tightly coupled LiDAR–IMU odometry and point-cloud registration produce drift-minimized state estimates and a locally consistent 3D map for navigation and planning.FAST-LIO2 integrates continuous IMU propagation with point-to-map residuals; an iterated Kalman filter updates the estimate from new measurements.Source: §4.3 · p. 14

4.4. Mapping

  • The mapping pipeline converts 3D points into a 2D occupancy map, a traversability-aware costmap, and a topological graph for high-level planning.The costmap combines static obstacles, dynamic changes, and obstacle safety margins.Source: §4.4 · pp. 15–16, Figure 6 · p. 15

4.5. Hierarchical Global Planning, Local Trajectory Optimization, and Execution Feedback

  • The system combines global route planning, local trajectory optimization, and execution feedback to maintain consistency among maps, plans, and executed motions.Dijkstra’s algorithm selects a global route from the costmap; runtime velocity-space search balances goal tracking, obstacle avoidance, and control smoothness.Source: §4.5 · p. 16

5. Building Layout Analysis and Optimization

The section evaluates how building layouts and depot placement affect delivery distance, using a hierarchical CVRP model to compare layouts and optimize depot locations. Results show that topology and demand distribution shape route costs, while depot relocation or additional depots can reduce distance.

5.1. Depot Location within a Single Layout

  • A demand-weighted centroid provides an initial depot estimate, followed by iterative search over candidate locations to minimize total delivery distance.The search evaluates each candidate using the proposed model’s Stage 1 cost and returns the lowest-cost location.Source: §5.1 · p. 17

5.2. Building Layout Typologies, Evaluation, and Depot Optimization

  • The evaluation considers grid, irregular, tree, and loop typologies, whose spatial organization affects delivery connectivity and travel distance.Figure 7 illustrates the representative typologies and depot adjustment behaviors under varying demand distributions.Source: §5.2 · p. 17, Figure 7 · p. 18
  • Loop layouts achieve the lowest distance with a central depot under symmetric or smoothly varying demand, while tree layouts are sensitive to depot placement and grid layouts tolerate it better.Irregular layouts increase path-length variability; adaptive relocation and multiple depots are particularly effective there.Source: §5.2 · pp. 17–18
  • Depot relocation toward high-demand regions or auxiliary depots in demand-intensive areas can substantially reduce total delivery distance, especially with limited path redundancy or uneven demand.Buildings are modeled as graph nodes, with inter-building costs computed using layout-specific shortest paths.Source: §5.2 · p. 18

6. Experiments and Results

The experiments verify the hierarchical planner across building, floor, and room configurations, including its feasibility and cost hierarchy. The tested room topologies produce different route costs, while the planner maintains trip optimality across the tested floor and room counts.

6.1.1. Hierarchical Optimal Solution

  • The hierarchical solution produced 16 building-level routes at Stage 1 and a total Stage 2 cost of 1260 across five buildings, with Stage 2 visit orders matching Stage 1 assignments.Stage 1 cost was 3400; sub-capacity Stage 2 routes were merged with Stage 1 routes as prescribed.Source: §6.1.1 · p. 20

6.1.2. Test Scenarios

  • The test scenarios varied building counts from 5 to 30, floor counts from one to 10, and room density, while retaining trip optimality across the tested floor and room configurations.The floor and room tests used 12 packages and capacity Q = 4, yielding three optimal trips in each case.Source: §6.1.2 · p. 21, Figure 11 · p. 23, Figure 12 · p. 23
  • Room-level costs were 42, 28, 30, and 28 for one-branch, loop, two-branch, and three-branch layouts, respectively; loop and three-branch layouts had the lowest costs.The one-branch layout incurred the highest cost through repeated corridor backtracking; loop connectivity avoids returning along the same path from terminal rooms.Source: §6.1.2 · pp. 21, 24

6.1. Algorithm Verification

  • Across architectural configurations, the planner generated feasible, near-optimal solutions and respected the building–floor–room cost hierarchy with privacy-aware penalties.The verification evaluated correctness, scalability, and hierarchical consistency.Source: §6.1 · p. 19, §6.1.2 · p. 24

6.2. Comparative Experiments

Comparative experiments test delivery-loop strategies, elevator cost models, vehicle capacities, and privacy-aware routing. The Hierarchical CVRP Model achieves the lowest reported total cost, while combined elevator costs produce more rational vertical transitions and privacy penalties prevent entry into restricted areas.

6.2.1. Comparative Analysis of Delivery Loop Strategies

  • The Sequential Baseline reduced total travel cost by 45.9% versus the Random Baseline, while the Hybrid strategy’s 40.2% cost reduction still left it inferior to the Sequential Baseline.The Hybrid strategy optimized inter-building routing but used randomized intra-building delivery sequences.Source: Figure 14 · p. 25, §6.2.1 · pp. 26–27
  • The Hierarchical CVRP Model reduced travel distance by 50.5% versus the Random Baseline and achieved the lowest total cost by jointly optimizing building capacity allocation and intra-building loops.Table 3 summarizes strategy travel costs; Figure 15 shows the inter-building routing patterns.Source: Figure 15 · p. 26, §6.2.1 · p. 27, Table 3 · p. 27

6.2.2. Comparison with Static Elevator Cost Modeling

  • Combining elevator waiting-time and floor-distance costs produced the most efficient and rational vertical-transition decisions among the four tested formulations.Waiting-time-only modeling still allowed avoidable floor changes, while floor-distance-only modeling could incur excessive elevator time.Source: §6.2.2 · p. 27, Figure 16 · p. 28

6.2.3. Comparison with Different Capacity Q

  • Larger vehicle capacities reduced the number of required trips and shifted the distribution of hierarchical travel costs.At Q = 1, each demand package required a single route.Source: §6.2.3 · p. 27, Figure 17 · p. 28

6.2.4. Comparison with Scheduling Without Privacy Constraints

  • Privacy-aware penalties prevented routes from entering restricted or socially sensitive zones, with a slight increase in inter-room distance cost.The comparisons show routes with and without privacy penalties and identify privacy-sensitive regions.Source: §6.2.4 · pp. 27, 30, Figure 18 · p. 29, Figure 19 · p. 29

6.3. Computational Efficiency

The computational evaluation examines solver behavior across building and demand scales and under uniform or heterogeneous inter-building distances. Larger problem scales increase computational burden, and heterogeneous distances slow convergence relative to fixed distances.

6.3. Computational Efficiency

  • The solver maintained stable performance across the evaluated scenarios on a compact computer with an AMD Ryzen 7 8745H processor.The system used a 16-core processor described as representative of on-site robotic deployment resources.Source: §6.3 · p. 30
  • As building count and per-building demand increase, computational burden rises; heterogeneous inter-building distances require more iterations for bounds to close than fixed distances.Under fixed distances, lazy constraints tighten feasibility rapidly near the optimal region, enabling fast convergence.Source: §6.3 · p. 30, Figure 20 · p. 30, Figure 21 · p. 31

6.4. Practical Deployment

The system was deployed in delivery missions across multiple buildings and floors. Field results report reliable operation across elevator transitions, dynamic corridors, and hierarchical delivery constraints.

6.4. Practical Deployment

  • Multiple real-world delivery missions validated the complete autonomous delivery system across several buildings and floors.Figure 22 shows a representative deployment scenario.Source: §6.4 · p. 31
  • Each mission starts at a centralized depot, proceeds through autonomous navigation and building access systems to the designated floor, and ends with locker-based parcel release at the target room.The robot continuously localizes and perceives its surroundings, avoiding static obstacles and dynamic human traffic.Source: §6.4 · p. 31
  • Field results show reliable elevator interaction and floor detection, consistent re-localization across vertical transitions, and collision-free corridor navigation with human presence.Task execution remained consistent under hierarchical, privacy, and access constraints, validating integration between route planning and motion control.Source: §6.4 · p. 31

7. Conclusion

The conclusion presents a Building–Floor–Room framework that decomposes large-scale building delivery routing while preserving global feasibility and consistency. It combines a building-aware CVRP model with a physical delivery system, and identifies theoretical bounds, multi-robot optimization, and uncertainty-aware planning as future work.

7. Conclusion

  • The Building–Floor–Room abstraction decomposes routing across spatial levels to reduce optimization complexity while preserving global feasibility and consistency.Figure 22 depicts a representative real-world deployment of the system.Source: §7 · p. 31, Figure 22 · p. 32
  • The building-aware CVRP models inter-building connectivity, inter-floor transitions, room-level access constraints, and privacy-sensitive regions.The model supports delivery-efficiency evaluation across building layouts and optimization of depot placement and room-level access strategies.Source: §7 · p. 32
  • The algorithms are instantiated in a delivery system integrating hierarchical planning with mapping, localization, and navigation, using a non-interactive privacy-preserving robot and reachability-aware distances.Multi-building and multi-floor experiments report reliable real-world performance and consistency between planning and physical execution.Source: §7 · p. 32
  • Future work will examine theoretical performance bounds, multi-robot cooperative optimization, and uncertainty-aware planning under dynamic demand and access constraints.Source: §7 · p. 32
Loading 2610.21361v1…