#import "../../lib/mod.typ": *

== Problem Definition <intro-problem-definition>
// #jonas[No difference from last here. A lot of this is copied directly from the original contract, and thus not relevant anymore. You do not have to spend time on this section.]

// // From the original contract:
// // 2. Problem Definition & Objectives
// // Efficient and safe approaches to multi-agent planning have been studied extensively, with many different approaches and assumptions about the environment and capabilities of the robotic agents. However, none of the existing approaches attempt to be able to operate in changing communication conditions, in a decentralized manner. Morteza[2], 2021, implements a modified A* algorithm that can handle dynamic obstacles in the environment. They also propose an architecture where the path planning optimization is done in a centralized manner on a cloud server. This reduces the number of messages sent between the agents but introduces a single point of failure. Xinjie[3], 2023, uses a game-theoretic approach to do path planning. Here agents cannot communicate with each other and instead have to predict how other agents will move based on the rules that govern the movement of the agents. Similar to how humans navigate in vehicle traffic, where the driver's own assumption/belief about how other drivers will follow the traffic law, is used to predict how other vehicles will move. Aalok[4], 2023, uses Gaussian Belief Propagation to do path planning for multiple agents. It is a decentralized approach using a data structure called a factor graph to model uncertainties about the position and velocity of other agents.

// // The objective of this project is to build on top of the work of [4], and extend it to handle cases with limited communication possibilities, challenging environments, and non-holonomic kinematic constraints. The environment will be a static indoor environment at a logistics facility where robots are integrated into a baggage sorting handling system. Instead of extending the original paper's source code, we will reimplement our version of the Gaussian Belief Propagation Planner algorithm from scratch. The intention of the rewrite is not only to try and improve performance but also to get a better understanding of the algorithm, to make it easier to extend it. The implemented solution will be tested in a simulated environment, with common scenarios found at logistic facilities, such as three-way junctions and intersections.

// Efficient and safe approaches to multi-agent planning have been studied extensively, with many different approaches and assumptions about the environment and capabilities of the robotic agents. However, none of the existing approaches attempt to be able to operate in changing communication conditions, in a decentralized manner. Morteza@kiadi_synthesized_2021, 2021, implements a modified A\* algorithm that can handle dynamic obstacles in the environment. They also propose an architecture where the path planning optimization is done in a centralized manner on a cloud server. This reduces the number of messages sent between the agents but introduces a single point of failure. Xinjie@liu_learning_2023, 2023, uses a game-theoretic approach to do path planning. Here agents cannot communicate with each other and instead have to predict how other agents will move based on the rules that govern the movement of the agents. Similar to how humans navigate in vehicle traffic, where the driver's own assumption/belief about how other drivers will follow the traffic law, is used to predict how other vehicles will move. Aalok@patwardhan_distributing_2023, 2023, uses Gaussian Belief Propagation to do path planning for multiple agents. It is a decentralized approach using a data structure called a factor graph to model uncertainties about the position and velocity of other agents.

// The objective of this project is to build on top of the work of @patwardhan_distributing_2023, and extend it to handle cases with limited communication possibilities#note.k[ehh...], challenging environments, and non-holonomic kinematic constraints#note.k[ehh...]. The environment will be a static indoor environment at a logistics facility where robots are integrated into a baggage sorting handling system. Instead of extending the original paper's source code, we will reimplement our version of the Gaussian Belief Propagation Planner algorithm from scratch. The intention of the rewrite is not only to try and improve performance but also to get a better understanding of the algorithm, to make it easier to extend it. The implemented solution will be tested in a simulated environment, with common scenarios found at logistic facilities, such as three-way junctions and intersections.

// #todo[Motivations for why our project is interesting]

// - What makes multi robot systems, better/more interesting than single robot systems?
// - What challenges does it bring with it?



// #todo[formulate a strong and clear definition of what path planning is, and ensure it is consistent with the rest of the document]



// - Peer to Peer based
// - No need to synchronize the ordering of messages in time
// - Modular. New factors can be added to the factor graph to encode different constraints.

The underlying problem addressed by this thesis is the inefficiency and limitations in existing multi-agent path planning systems, particularly in complex environments. Current systems often struggle with issues related to collision avoidance, especially in context of multi-agent applications, and effective navigation through constrained and complex spaces. These challenges are exacerbated by the lack of robust, flexible, and extendable simulation frameworks that can accurately reproduce and enhance existing path planning algorithms. Furthermore, in the subfield of #acr("GBP") collaborative planning algorithms, which is still a quite new field, there is lack of automated global planning capabilities. The problem of integrating global planning with #acr("GBP") comes with further challenges, and it is important to consider possible solutions, in such a way that it does not compromise the performance of the system. This thesis seeks to solve these problems by developing a comprehensive solution that enhances the usability, functionality, and scalability of multi-agent path planning systems in the context of #acr("GBP") algorithms. The solution offered by this thesis is the simulation tool #acr("MAGICS"), which is based off of the work done in #gbpplanner, and extends it further.

// be implemented in a simulated environment, and evaluated based on a set of predefined metrics.
