Ing. Kristýna Janovská

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.