Keisuke Okumura

Keisuke Okumura

Auto-generated profile, based on publicly available information

Keisuke Okumura

Artificial Intelligence Research Center, National Institute of Advanced Industrial Science and Technology (AIST), Tokyo, Japan

Research Focus & Metrics

Academic Career Length

18Years (2009-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
3 July 2022 in Artificial Intelligence
Verified
Journal Article
Open access
KOKeisuke Okumura
Keisuke Okumura
MMManao Machida
Manao Machida
XDXavier Défago
Xavier Défago
YTYasumasa Tamura
Yasumasa Tamura

22 April 2024 in IEEE Access
Verified
Journal Article
Open access
JAJean-Marc Alkazzi
Jean-Marc Alkazzi
KOKeisuke Okumura
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.

1 August 2019
Verified
Conference Paper
Closed access
KOKeisuke Okumura
Keisuke Okumura
MMManao Machida
Manao Machida
XDXavier Défago
Xavier Défago
YTYasumasa Tamura
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.

22 May 2023 in Artificial Intelligence
Verified
Journal Article
Closed access
KOKeisuke Okumura
Keisuke Okumura
XDXavier Défago
Xavier Défago

5 April 2023 in IEEE Transactions on Robotics
Verified
Journal Article
Open access
KOKeisuke Okumura
Keisuke Okumura
FBFrançois Bonnet
François Bonnet
YTYasumasa Tamura
Yasumasa Tamura
XDXavier Défago
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.

27 September 2021
Verified
Conference Paper
Open access
KOKeisuke Okumura
Keisuke Okumura
YTYasumasa Tamura
Yasumasa Tamura
XDXavier Defago
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.