KOKeisuke Okumura

Keisuke Okumura

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Keisuke Okumura has a total of 27 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Denoising Multirobot Trajectories

    by Yuhao Zhang, Keisuke Okumura, Ajay Shankar, Amanda Prorok

  • 100-Mouse System: Scalable Multi-Robot Testbed with State Management User Interface

    by Shota Yamamoto, Ryusei Matsumoto, Yoko Sasaki, Keisuke Okumura

    Multi-robot systems are expected to underpin the future of automated infrastructure in various fields, including logistics and transportation. Despite the importance of multi-robot research, operating a large number of physical robots presents nontrivial challenges that exceed those encountered in simulation environments. These include communication saturation, the difficulties in real-time localization, detection of abnormal robot behavior, and the need for user-friendly interfaces to allow for effective state management. Collectively, they create a significant gap in the assumptions between lab-scale studies and deployable technologies in this field. Therefore, we developed a versatile testbed for multi-robot studies that can accommodate up to 100 differential-drive robots, called the 100-Mouse System . Our hallmark is scalability, while maintaining flexibility to allow researchers to test their ideas with actual robot fleets. This is a result of deliberately and integrally designed modules from both software and hardware perspectives, as well as a user interface, which is essential in large-scale experiments. As an application of this platform, we present a pattern formation task in a centralized manner, demonstrating the ability of the system to effectively accommodate large robot fleets.

  • Open Access

    Congestion Mitigation Path Planning for Large-Scale Multi-Agent Navigation in Dense Environments

    by Takuro Kato, Keisuke Okumura, Yoko Sasaki, Naoya Yokomachi

    In high-density environments where numerous autonomous agents move simultaneously in a distributed manner, streamlining global flows to mitigate local congestion is crucial to maintain overall navigation efficiency. This paper introduces a novel path-planning problem, congestion mitigation path planning (CMPP), which embeds congestion directly into the cost function, defined by the usage of incoming edges along agents' paths. CMPP assigns a flow-based multiplicative penalty to each vertex of a sparse graph, which grows steeply where frequently-traversed paths intersect, capturing the intuition that congestion intensifies where many agents enter the same area from different directions. Minimizing the total cost yields a set of coarse-level, time-independent routes that autonomous agents can follow while applying their own local collision avoidance. We formulate the problem and develop two solvers: (i) an exact mixed-integer nonlinear programming solver for small instances, and (ii) a scalable two-layer search algorithm, A-CMTS, which quickly finds suboptimal solutions for large-scale instances and iteratively refines them toward the optimum. Empirical studies show that augmenting state-of-the-art collision-avoidance planners with CMPP significantly reduces local congestion and enhances system throughput in both discrete- and continuous-space scenarios. These results indicate that CMPP improves the performance of multi-agent systems in real-world applications such as logistics and autonomous-vehicle operations.


  • Open Access

    A Comprehensive Review on Leveraging Machine Learning for Multi-Agent Path Finding

    by Jean-Marc Alkazzi, Keisuke Okumura

    This review paper provides an in-depth analysis of the latest advancements in applying Machine Learning (ML) to solve the Multi-Agent Path Finding (MAPF) problem. The MAPF problem is about finding collision-free paths for multiple agents to travel from their source to goal locations in a known environment. This method underpins a range of advanced, large-scale automated systems, notably in warehouse logistics. The existing research on conventional MAPF is extensive; however, recent developments in ML have notably augmented the capabilities of MAPF techniques. This research seeks to thoroughly investigate the emerging field focused on using ML to help solve the MAPF problem. It aims to highlight the transformative potential of ML in enhancing the efficiency and effectiveness of multi-agent systems in navigating and coordinating in complex environments. Our study comprehensively examines the entire MAPF process, encompassing environment representation, path planning, and solution execution.


  • Open Access

    Offline Time-Independent Multiagent Path Planning

    by Keisuke Okumura, François Bonnet, Yasumasa Tamura, Xavier Défago

    This study examines a novel planning problem for multiple agents that cannot share holding resources, named Offline Time-Independent Multiagent Path Planning (OTIMAPP) . Given a graph and a set of start-goal pairs, the problem to be addressed is assigning a path to each agent, such that every agent eventually reaches its destination without blocking others, regardless of when each agent starts and finishes each own action. This motivation stems from timing uncertainties, including the reality gaps between planning and robot execution. In contrast to conventional solution, concepts of multirobot path planning that rely on timings, once OTIMAPP solutions are obtained, they can be executed without any synchronization between robot actions. Moreover, there is a theoretical guarantee that all robots eventually reach their destinations, provided they avoid interrobot collisions. This study attempts to establish OTIMAPP both theoretically and practically. Specifically, we present a formalization of the problem, solution conditions based on a categorization of deadlocks, computational complexities showing that OTIMAPP is computationally intractable, practical relaxation of the solution concept, two algorithms to solve OTIMAPP based on multiagent pathfinding algorithms, empirical results showing large OTIMAPP instances can be solved to some extent, as well as robot demonstrations of asynchronous OTIMAPP execution.


  • Top Cited Papers
    Open Access

    Priority inheritance with backtracking for iterative multi-agent path finding

    by Keisuke Okumura, Manao Machida, Xavier Défago, Yasumasa Tamura


  • Open Access

    Iterative Refinement for Real-Time Multi-Robot Path Planning

    by Keisuke Okumura, Yasumasa Tamura, Xavier Defago

    We study the iterative refinement of path planning for multiple robots, known as multi-agent pathfinding (MAPF). Given a graph, agents, their initial locations, and destinations, a solution of MAPF is a set of paths without collisions. Iterative refinement for MAPF is desirable for three reasons: 1) optimization is intractable, 2) sub-optimal solutions can be obtained instantly, and 3) it is anytime planning, desired in online scenarios where time for deliberation is limited. Despite the high demand, this is under-explored in MAPF because finding good neighborhoods has been unclear so far. Our proposal uses a sub-optimal MAPF solver to obtain an initial solution quickly, then iterates the two procedures: 1) select a subset of agents, 2) use an optimal MAPF solver to refine paths of selected agents while keeping other paths unchanged. Since the optimal solvers are used on small instances of the problem, this scheme yields efficient-enough solutions rapidly while providing high scalability. We also present reasonable candidates on how to select a subset of agents. Evaluations in various scenarios show that the proposal is promising; the convergence is fast, scalable, and with reasonable quality.


  • Open Access

    Investigating the Hand Ownership Illusion With Two Views Merged in

    by Keisuke Okumura, Hiroki Ora, Yoshihiro Miyake

    Researchers investigating virtual/augmented reality have shown humans' marked adaptability, especially regarding our sense of body ownership; their cumulative findings have expanded the concept of what it means to have a body. Herein, we report the hand ownership illusion during “two views merged in.” In our experiment, participants were presented two first-person perspective views of their arm overlapped, one was the live feed from a camera and the other was a playback video of the same situation, slightly shifted toward one side. The relative visibility of these two views and synchrony of tactile stimulation were manipulated. Participants' level of embodiment was evaluated using a questionnaire and proprioceptive drift. The results show that the likelihood of embodying the virtual hand is affected by the relative visibility of the two views and synchrony of the tactile events. We observed especially strong hand ownership of the virtual hand in the context of high virtual hand visibility with synchronous tactile stimulation.


  • Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding

    by Keisuke Okumura, Manao Machida, Xavier Défago, Yasumasa Tamura

    The Multi-agent Path Finding (MAPF) problem consists in all agents having to move to their own destinations while avoiding collisions. In practical applications to the problem, such as for navigation in an automated warehouse, MAPF must be solved iteratively. We present here a novel approach to iterative MAPF, that we call Priority Inheritance with Backtracking (PIBT). PIBT gives a unique priority to each agent every timestep, so that all movements are prioritized. Priority inheritance, which aims at dealing effectively with priority inversion in path adjustment within a small time window, can be applied iteratively and a backtracking protocol prevents agents from being stuck. We prove that, regardless of their number, all agents are guaranteed to reach their destination within finite time, when the environment is a graph such that all pairs of adjacent nodes belong to a simple cycle of length 3 or more (e.g., biconnected). Our implementation of PIBT can be fully decentralized without global communication. Experimental results over various scenarios confirm that PIBT is adequate both for finding paths in large environments with many agents, as well as for conveying packages in an automated warehouse.