Ing. Kristýna Janovská

Stať ve sborníku

10.1007/978-3-031-94989-0_6

Katedra teoretické informatiky
Katedra aplikované matematiky

We revisit rule-based algorithms for multi-agent path finding (MAPF) where the task is being solved by applying a fixed set of movement primitives. MAPF is a task of navigating agents from their initial positions to given individual goal positions via non-conflicting paths. The environment in which agents move is modeled as an undirected graph with agents in its vertices. Rule-based algorithms we study in this paper are complete, polynomial-time, and sub-optimal with respect to common cumulative objectives used in MAPF such as makespan or sum-of-costs. Out contribution consists in a new step that pre-processes the input graph by decomposing it into highly connected components via spectral clustering. Agents are moved to their goal cluster first before the rule-based algorithm is applied. The benefit of this approach is twofold: (1) the algorithms are often more efficient on highly connected clusters and (2) we can potentially run the algorithms in parallel on individual clusters.

Stať ve sborníku

10.5220/0014248800004052

Katedra teoretické informatiky
Katedra aplikované matematiky

We address the problem of smooth continuous multi-agent path finding (SC-MAPF), where agents move in a continuous environment along smooth curves in continuous time. The paths for individual agents are searched in local visibility roadmaps that consider obstacles and other agents. A new algorithm is proposed in this work, which combines the previous algorithm CE-CBS for high-level search with any-angle path finding for local single-agent planning, where agents are to avoid obstacles, both static and other agents. The new algorithm is tested and compared to CE-CBS, the algorithm building individual paths using RRT∗, and SMT-CCBS algorithm, an algorithm for MAPFR. Experimental results show various advantages of the new algorithm over CE-CBS and SMT-CCBS in comparable settings.

Stať ve sborníku

10.1109/ICTAI62512.2024.00105

Katedra aplikované matematiky

We address a variant of multi-agent path finding in continuous environment (SC-MAPF), where agents move along sets of smooth curves. Collisions between agents are resolved via avoidance in the space domain. In this work a new Continuous Environment Conflict-Based Search (CE-CBS) algorithm is proposed. CE-CBS combines conflict-based search (CBS) for the high-level search framework with RRT* for low-level path planning. The CE-CBS algorithm is tested under various settings on various SC-MAPF instances. Experimental results show that CE-CBS is competitive w.r.t. other algorithms that consider the continuous aspect in MAPF such as MAPF with continuous time.

Stať ve sborníku

10.1609/socs.v17i1.31581

Katedra aplikované matematiky

We address rule-based algorithms for multi-agent path finding (MAPF). MAPF is a task of finding non-conflicting paths connecting agents' initial and goal positions in a shared environment specified via an undirected graph. Rule-based algorithms use a fixed set of predefined primitive operations to move agents to their goal positions in a complete manner. We propose to apply spectral clustering on the underlying graph to decompose the graph into highly connected components and move agents to their goal cluster first before the rule-based algorithm is applied. The benefit of this approach is twofold: (1) the rule-based algorithms are often more efficient on highly connected clusters and (2) we can potentially run the algorithms in parallel on individual clusters.

Článek

10.1007/s42979-022-01437-x

Katedra aplikované matematiky

We address the problem of evacuation from the perspective of agent-based modeling (ABM) in this paper. The evacuation problem is modeled as a navigation of multiple agents that spatially interact with each other in a known environment. The environment is divided into a danger and a safe zone while the task of agents is to move from the danger zone to the safe one in a collision-free manner. Unlike previous approaches that model the environment as a discrete graph with agents placed in its vertices, at most one agent per vertex, our approach adopts various continuous aspects such as a grid-based embedding of the environment into 2D space and continuous line of sight of agents. In addition to this, we adopt hierarchical structure of multi-agent system in which so called leading agents are more informed having full knowledge of other agents and are capable of performing multi-agent pathfinding (MAPF) via centralized algorithms like conflict-based search (CBS) while so called follower agents with limited knowledge about other agents are modeled using simple local rules. Our experimental evaluation indicates that suggested hierarchical modeling approach can serve as a tool for studying the progress and the efficiency of evacuation processes in different environments.

Stať ve sborníku

10.5220/0012206800003543

Katedra aplikované matematiky

We focus on rule-based algorithms for multi-agent path finding (MAPF) in this paper. MAPF is a task of finding non-conflicting paths connecting agents’ specified initial and goal positions in a shared environment specified via an undirected graph. Rule-based algorithms use a fixed set of predefined primitives to move agents to their goal positions in a complete manner. We propose to apply spectral clustering on the underlying graph to decompose the graph into highly connected component and move agents to their goal cluster first before the rule-based algorithm is applied. The benefit of this approach is twofold: (1) the algorithms are often more efficient on highly connected clusters and (2) we can potentially run the algorithms in parallel on individual clusters.

Stať ve sborníku

10.1609/socs.v15i1.21790

Katedra aplikované matematiky

We address the problem of evacuation from the heuristic search perspective combined with agent-based modeling (ABM). The evacuation problem is modeled as a navigation of multiple agents in a known environment. The environment is divided into a danger and a safe zone while the task of agents is to move from the danger zone to the safe zone in a collision-free manner. Unlike previous approaches that model the environment as a discrete graph with agents placed in its vertices, at most one agent per vertex, our approach adopts various continuous aspects such as a grid-based embedding of the environment into 2D space and continuous line of sight of agents. In addition to this, we adopt hierarchical structure of our multi-agent system in which so called leading agents are more informed and are capable of performing multi-agent pathfinding (MAPF) via centralized algorithms like conflict-based search (CBS) while so called following agents with limited knowledge about other agents are modeled using simple local rules. Our experimental evaluation indicates that suggested hierarchical modeling approach can serve as a tool for studying the progress and the efficiency of evacuation processes in different environments.

Stať ve sborníku

10.5220/0010678200003064

Katedra aplikované matematiky

The problem of evacuation is addressed from the perspective of agent-based modeling (ABM) in this paper. We study evacuation as a problem of navigation of multiple agents in a known environment. The environment is divided into a danger and a safe zone while the task of agents is to move from the danger zone to the safe one. Unlike previous approaches that model the environment as a discrete graph with agents placed in its vertices our approach adopts various continuous aspects such as grid-based embedding of the environment into 2D space continuous line of sight of an agent. In addition to this, we adopt hierarchical structure of multi-agent system in which so called leading agents are more informed and are capable of performing multiagent pathfinding (MAPF) via centralized algorithms like conflict-based search (CBS) while so called follower agents are modeled using simple local rules. Our experimental evaluation indicates that suggested modeling approach can serve as a tool for studying the progress and the efficiency of the evacuation process.