Distributed Multi-Agent Pathfinding

Multi-agent path finding (MAPF) is the task of finding non-conflicting paths for multiple agents that operate in a environment with shared resources. <br/>Finding an optimal solution quickly becomes intractable for many applications and consequently suboptimal methods are also explored extensively in literature. <br/>This work presents the...

Routing based on User Requirements

The versatility of the internet enables many applications that play an increasingly bigger role in our society. However, users have little control over the route that their internet traffic takes, which prevents them from controlling who sees their packets and how their traffic is handled. Researchers have proposed an extension to the internet,...

Autonomous assembly of digital materials: with inchworm locomotion robotic assemblers

Throughout history, human progress has been defined by the mastery of materials, transitioning from stone and bronze to the steel age. However, this progression has not only been defined by the materials utilized but has also encompassed a shift in processes, moving from the industrial to the information era. Despite the advances in fabrication...

Designing the Concurrent Searching and Pathfinding Algorithm for Swarm Robotics

The problem of finding a target and forming a path to it is known and is well-explored in the field of swarm robotics. Using swarm intelligence, even swarms of simple robots are capable of solving this problem. However, often these works assume that two robots can perceive each other can physically reach each other, or that robots can detect any...

Solving the Colored Multi-Agent Path Finding with Waypoints Problem using SAT

The Multi-Agent Path Finding (MAPF) problem is the problem of planning paths for multiple agents without any collisions. There are also many variants such as the waypoint variant, where each agent also has a set of waypoints it must visit before reaching its goal. The colored variant, in which the agents are grouped into teams and each team has...

Using voxelised spaces for the generation and visualisation of dynamic evacuation routes

In the modern world, evacuating a building in a safe and orderly manner remains a challenge. Fire-based emergencies in a building are dynamic environments that can be simulated to better understand, analyse, and contribute to safer and smarter buildings. While different spatial representations exist, <i>voxels</i> provide a structured, flexible...

Matching in Multi-Agent Pathfinding using M*

Multi-agent pathfinding (MAPF) is the process of finding collision-free paths for multiple agents. MAPF can be extended by grouping agents into teams. In a team, agents need to be assigned (or matched) to one of the team's goals such that the sum of individual cost} is minimised. This extension is called MAPF with matching (MAPFM). M* is a...

Multi-Agent Pathfinding with Matching using Increasing Cost Tree Search

Both the assignment problem and the multi-agent pathfinding problem are common problems in the fields of robotics and transportation. The joint problem of multi-agent pathfinding extended with the assignment of goals to agents, matching, is something that has not been studied much; few methods exist today that solve it. In this work, two types...

Multi-Agent Pathfinding with Matching using Enhanced Partial Expansion A*

For the Multi-Agent Pathfinding (MAPF) problem, a set of non-colliding paths must be found for multiple agents. In Multi-Agent Pathfinding with Matching (MAPFM), this problem is extended: agents and goals are added to a team and each agent has to navigate to a goal that belongs to the same team. In this paper, two extensions of the EPEA* MAPF...

Solving Multi-Agent Pathfinding with Matching using A*+ID+OD

This paper extends the Multi-Agent Pathfinding (MAPF) algorithm, A*+ID+OD, to be able to solve problems with matching. This extension still keeps the optimal and completeness properties of the original algorithm. Matching is added to the algorithm in both an exhaustive and heuristic manner. Exhaustive matching is further improved by adding a new...

Multi-agent pathfinding with waypoints using Branch-Price-and-Cut

In the multi-agent pathfinding (MAPF) problem, agents have to traverse a graph to a goal location without running into each other. Currently, the Branch-and-Cut-and-Price-MAPF (BCP-MAPF) algorithm is the state-of-the-art algorithm for solving MAPF problems, which uses Branch-Price-and-Cut (BPC) to solve a linear minimization problem. The multi...

Solving the Multi-Agent Path Finding with Waypoints Problem Using Subdimensional Expansion

Little to no research has been done on the multi-agent path finding with waypoints problem (MAPFW) even though it has many important real world applications. In this paper we extend an existing algorithm for the multi-agent path finding problem (MAPF) called M* \cite{New}. We do so by ordering the waypoints using a Travelling salesman problem...

Analysis of the influence of graph characteristics on MAPFW algorithm performance

The Multi-Agent Path Finding (MAPF) problem is a problem in which a route must be found for multiple agents such that they do not collide. The Multi-Agent PathFinding with Waypoints problem extends this problem by adding waypoints that the agents must visit before travelling to their end location. This paper compares five algorithms for MAPF...

Extending the Multi-Label A* Algorithm for Multi-Agent Pathfinding with Multiple Waypoints

Multi-Agent Pathfinding (MAPF) is a problem in which the goal is to plan paths for distinct agents while avoiding collisions between agents. We consider a new variation of MAPF, namely MAPF with multiple waypoints (MAPFW), where agents are required to visit a set of intermediary locations before visiting their end goal. MAPFW may have...

A Rapid Grid-Search Technique for KBO Exploration Trajectories

The Kuiper Belt is considered to be formed by remnants of the original Solar System, that is why exploration missions to that region are susceptible of having an enormous scientific impact. Nonetheless, it is far away from Earth, missions to KBO targets a significant challenge. Additionally, current methods to identify trajectories that...

Indoor A* Pathfinding through an Octree Representation of a Point Cloud

There is a growing demand of 3D indoor pathfinding applications. Researched in the field of robotics during the last decades of the 20th century, these methods focussed on 2D navigation. Nowadays we would like to have the ability to help people navigate inside buildings or send a drone inside a building when this is too dangerous for people....

Semantic enrichment of a point cloud based on an octree for multi-storey pathfinding

Acquiring point clouds of indoor environments became increasingly accessible in recent years. However, the resulting 3D point cloud data is unstructured, and does not contain enough information to be useful for complex tasks like pathfinding. Indoor models which are currently derived from point clouds do not include furniture and stairs. The...