Author name cluster

Florence Ho

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

IROS Conference 2024 Conference Paper

Dual-Process Optimization for Multi-Vehicle Route Planning and Parts Collection Sequencing

Ryota Higa
Takuro Kato
Florence Ho

We proposed a novel dual-process optimization approach for parts collection order and route planning in parts warehouses. Conventional multi-agent parts collection typically uses the vehicle routing problem (VRP), which focuses on minimizing the number of agents and costs. However, the model does not fully leverage the vehicle’s potential. Moreover, multi-agent path finding (MAPF) focuses on route planning and avoiding path conflicts, ignoring the order of part collection. The proposed approach integrates algorithms from the traveling salesman problem (TSP) and path planning, and modifies them to suit the dynamic and complex environment of parts warehouses. This integration streamlines the collection process and considerably reduces the operational time. Thus, the study can improve automation and efficiency in parts warehouse management and improve optimization techniques. The proposed method achieved more than tenfold acceleration compared with the ideal centralized optimization, without cost increments. As the number of agents and part collections increases, centralized optimization requires a metaheuristic approach, which results in solution degradation. However, the proposed approach maintains over tenfold acceleration and produces solutions with shorter operational times. Furthermore, we conducted an ablation study comparing six methods, from entirely independent to centralized optimization, demonstrating that the proposed approach effectively balances computational time and solution accuracy.

Details

AAMAS Conference 2023 Conference Paper

Preference-Based Multi-Objective Multi-Agent Path Finding

Florence Ho
Shinji Nakadai

Multi-Agent Path Finding (MAPF) consists in computing a set of collision-free paths for a team of agents on a given graph while minimizing one objective, such as the sum of paths costs or the makespan. However, real-world applications may require the consideration of multiple objectives. Thus, in this work, we propose to address a novel extension of MAPF, Scalarized Multi-Objective MAPF (MOMAPF), that aims to optimize multiple given objectives while computing collision-free paths for all agents and incorporating the preferences of a decision maker over each objective. The preferences of a decision maker are reflected by a weight value associated to each objective and all weighted objectives are combined into one scalar to minimize. We introduce a solver for Scalarized MOMAPF based on Conflict-Based Search (CBS), Scalarized MO-CBS, that incorporates an adapted path planner based on an evolutionary algorithm, the Genetic Algorithm (GA). We also introduce three practical objectives to consider in path planning: efficiency, safety, and smoothness. We evaluate the performance of our proposed method in function of the input parameters of GA on experimental simulations.

PDF

IROS Conference 2022 Conference Paper

Extended Time Dependent Vehicle Routing Problem for Joint Task Allocation and Path Planning in Shared Space

Aayush Aggarwal
Florence Ho
Shinji Nakadai

We address the joint task allocation and path planning problem whereby an operator with a fleet of vehicles must assign multiple tasks to each vehicle, while ensuring collision-free paths for them such that the total travel cost is minimized. Instead of sequentially solving the task allocation problem first, and then resolving all predicted collisions, i. e. conflicts between vehicles, we propose a novel method that solves in a simultaneous way task allocation and multi-agent path planning. Specifically, we introduce an extension of the Time Dependent Vehicle Routing Problem (TDVRP) whereby we propose to integrate conflicts information into a time dependent cost function used in the task allocation resolution. We compare our approach to two baseline approaches that both use a standard Capacitated VRP (CVRP) solver, a “one-shot” method and a “multi-shot” method. We perform simulations on benchmark realistic warehouse scenarios and the obtained results show that our proposed approach is able to generate improvements in the solutions costs compared to the baseline approaches.

Details

JAAMAS Journal 2022 Journal Article

Preference-based multi-objective multi-agent path finding

Florence Ho
Shinji Nakadai

Abstract Multi-Agent Path Finding (MAPF) is a well-studied problem that aims to generate collision-free paths for multiple agents while optimizing a single objective. However, many real-world applications require the consideration of multiple objectives. In this paper, we address a novel extension of MAPF, Multi-Objective MAPF (MOMAPF), that aims to optimize multiple given objectives while computing collision-free paths for all agents. In particular, we aim to incorporate the preferences of a decision maker over multi-agent path planning. Thus, we propose to solve a scalarized MOMAPF, whereby the given preferences of a decision maker are reflected by a weight value associated to each given objective and all weighted objectives are combined into one scalar. We introduce a solver for scalarized MOMAPF based on Conflict-Based Search (CBS) that incorporates an adapted path planner based on an evolutionary algorithm, the Genetic Algorithm (GA). We also introduce three practical objectives to consider in path planning: efficiency, safety, and smoothness. We evaluate the performance of our proposed method in function of the input parameters of GA on experimental simulations and we analyze its efficiency in providing conflict-free solutions within a fixed time.

Details DOI

AAMAS Conference 2019 Conference Paper

Multi-Agent Path Finding for UAV Traffic Management

Florence Ho
Ana Salta
Ruben Geraldes
Artur Goncalves
Marc Cavazza
Helmut Prendinger

Unmanned aerial vehicles (UAVs) are expected to provide a wide range of services, whereby UAV fleets will be managed by several independent service providers in shared low-altitude airspace. One important element, or redundancy, for safe and efficient UAV operation is pre-flight Conflict Detection and Resolution (CDR) methods that generate conflict-free paths for UAVs before the actual flight. Multi-Agent Path Finding (MAPF) has already been successfully applied to comparable problems with ground robots. However, most MAPF methods were tested with simplifying assumptions which do not reflect important characteristics of many real-world domains, such as delivery by UAVs where heterogeneous agents need to be considered, and new requests for flight operations are received continuously. In this paper, we extend CBS and ECBS to efficiently incorporate heterogeneous agents with computational geometry and we reduce the search space with spatio-temporal pruning. Moreover, our work introduces a “batching” method into CBS and ECBS to address increased amounts of requests for delivery operations in an efficient manner. We compare the performance of our “batching” approach in terms of runtime and solution cost to a “first-come first-served” approach. Our scenarios are based on a study on UAV usage predicted for 2030 in a real area in Japan. Our simulations indicate that our proposed ECBS based “batching” approach is more time efficient than incremental planning based on Cooperative A*, and hence can meet the requirements of timely and accurate response on delivery requests to users of such UTM services.

PDF

AAMAS Conference 2018 Conference Paper

Simulating Shared Airspace for Service UAVs with Conflict Resolution

Florence Ho
Ruben Geraldes
Artur Gon�alves
Marc Cavazza
Helmut Prendinger

In future UAV-based services, UAV fleets will be managed by independent service providers in shared low-altitude airspace. Therefore, Conflict Detection and Resolution (CDR) methods that solve conflicts, i. e. possible collisions, between UAVs of all service providers are a key element of the Unmanned Aircraft System Traffic Management (UTM) system. We present a top-to-bottom algorithmic system with an extension to UAV operations of ORCA, a state-ofthe-art algorithm in robotics. Then, using extreme-conflict situations, we empirically determine optimal parameter values for our adapted ORCA, and we observe a better performance compared to the standard use of ORCA. Finally, using realistic UAV traffic situations for delivery, we perform extensive simulations to study the potential occurrence and distribution of collisions, and to assess safety parameters for CDR.

PDF