Lifelong multiagent path finding (LMAPF) requires continuous task assignment and collision-free path planning for large robot fleets. However, existing LMAPF methods assume synchronous unit-time actions, whereas real robots execute movements asynchronously with nonuniform durations. This mismatch can lead to execution-time collisions and makes frequent replanning challenging in large-scale systems. We study LMAPF with asynchronous actions and present a framework that ensures safety under asynchronous execution and real-time scalability through coordinated path planning and action scheduling, complemented by a simple greedy task allocation. To ensure safety, the path planner eliminates cycle conflicts to prevent structural deadlocks, while a lightweight action scheduler enforces vertex precedence during execution, resolving following conflicts without explicit temporal modeling. To achieve real-time performance, the planner performs partial replanning by reusing the residual paths of nonidle agents, which are converted into a synchronous form through the scheduler’s path resynchronization, enabling consistent and efficient replanning. Experiments in warehouse environments with up to 1000 robots demonstrate that our framework more than doubles throughput compared with state-of-the-art LMAPF methods, while maintaining safe operations under asynchronous actions.

Target singulation involves a rearrangement of surrounding obstacles to create space for grasping the target. However, when objects are tightly packed in a confined workspace (i.e., a limited table boundary), it is not easy to relocate obstacles. Using non-prehensile manipulation, such as push, is suitable for creating space when objects are closely placed. However, it can be risky as collisions between objects might unintentionally push them beyond the table boundary. On the other hand, prehensile motion ensures safe relocation of objects. However, the objects that can be safely grasped are limited when the packing density is too high. Thus, it may not find a rearrangement plan for target singulation. To complement both methods, we suggest using collision-free push-stack synergy for rearrangement. Collision-free push prevents objects from moving out of the boundary while efficiently relocating objects and stack creates space in advance to safely push. Furthermore, we propose a modified algorithm of Local Obstacle-based Backward Search (LOBS), which generates a global rearrangement plan using only pick-and-place actions. To evaluate our method, we set up challenging scenarios - with a packing density of 50% and up to 70 objects. Compared to LOBS, the success rate increased significantly with no meaningful increase in planning time. Additionally, Our method outperformed other baselines as well.

Meta's data center networks have relied on BGP for routing and interconnectivity due to its scalability and simplicity. However, as our network evolves, BGP's limitations in supporting complex network migrations have become apparent. These migrations require customized routing at each intermediate step, considering topological properties. In this paper, we highlight the unique challenges of production migration and illustrate how native BGP falls short, unable to encode both sequential and spatial conditions. To address this challenge, we introduce a novel Route Planning Abstraction (RPA) that augments the BGP protocol to support migration. It enables centralized route planning while maintaining distributed enforcement. We demonstrate the power of this abstraction by developing Centralium, a hybrid route-planning framework with a centralized controller, and over ten use cases to support various migrations in production. Our production experience with Centralium, deployed alongside BGP in large-scale data centers, has shown substantial reduction in the time and risk of network migration operations.

When multiple tablewares are closely packed on a table, rearranging obstacles to make space is necessary to grasp the target, often called target singulation. Due to the nature of handling fragile tablewares (i.e. plates, bowls), we make a few assumptions for the target singulation problem. First, tableware is grasped with a multi-fingered gripper; second, rearrangement is based on prehensile motions like pick-and-place. Under these assumptions, we aim to generate a relocation plan that guarantees global optimality. Furthermore, if any relocation plan cannot singulate the target, we aim to determine it quickly. Therefore, we propose a search method that utilizes the relationship between the object and its nearby obstacles expressed in propositional logic. We define the problem as determining logical entailment (i.e., whether the target can be singulated) and expand the search tree from the target while generating an optimal relocation plan. We demonstrate the performance of our algorithm by increasing the number of objects and validate the plan in a simulation environment.

Determining a feasible path for nonholonomic mobile manipulators operating in congested environments is challenging. Sampling-based methods, especially bi-directional tree search-based approaches, are amongst the most promising candidates for quickly finding feasible paths. However, sampling uniformly when using these methods may result in high computation time. This paper introduces two techniques to accelerate the motion planning of such robots. The first one is coordinated focusing of samples for the manipulator and the mobile base based on the information from robot surroundings. The second one is a heuristic for making connections between the two search trees, which is challenging owing to the nonholonomic constraints on the mobile base. Incorporating these two techniques into the bi-directional RRT framework results in about 5x faster and 10x more successful computation of paths as compared to the baseline method.

Large content providers build points of presence around the world, each connected to tens or hundreds of networks. Ideally, this connectivity lets providers better serve users, but providers cannot obtain enough capacity on some preferred peering paths to handle peak traffic demands. These capacity constraints, coupled with volatile traffic and performance and the limitations of the 20 year old BGP protocol, make it difficult to best use this connectivity.