## Expand description

CaBooSe (Conflict-Based Search) is a crate implementing the
*Continuous Conflict-Based Search* algorithm (CCBS) for the
*Multi-Agent Path Finding* problem (MAPF).
It uses the *Safe Interval Path Planning* algorithm (SIPP)
algorithm under the hood to plan individual paths while avoiding
already processed collisions. Furthermore, SIPP itself uses the
*Reverse Resumable A** algorithm (RRA*) to compute heuristics
for each task to solve.

### §Usage

The main entry point of the crate is the `ConflictBasedSearch`

struct, which
requires a `TransitionSystem`

to be created. It can then be used to plan paths
for a set of agents, by calling the `ConflictBasedSearch::solve`

function on a
`CbsConfig`

that gathers all the information needed to solve the problem.

#### §Example

```
use ordered_float::OrderedFloat;
use std::sync::Arc;
use caboose::{
simple_graph, SimpleWorld, SimpleState, SimpleHeuristic, GraphNodeId, GraphEdgeId,
ConflictBasedSearch, CbsConfig, Task,
};
let size = 10;
let graph = simple_graph(size);
let transition_system = Arc::new(SimpleWorld::new(graph, 0.4));
let tasks = vec![
Arc::new(Task::new(
SimpleState(GraphNodeId(0)),
SimpleState(GraphNodeId(9)),
OrderedFloat(0.0),
)),
Arc::new(Task::new(
SimpleState(GraphNodeId(9)),
SimpleState(GraphNodeId(0)),
OrderedFloat(0.0),
)),
];
let config: CbsConfig<
SimpleWorld,
SimpleState,
GraphEdgeId,
OrderedFloat<f64>,
OrderedFloat<f64>,
SimpleHeuristic,
> = CbsConfig::new(
transition_system.clone(),
tasks,
OrderedFloat(1e-6),
1,
None,
);
let mut solver = ConflictBasedSearch::new(transition_system.clone());
let solutions = solver.solve(&config).unwrap();
```

### §Lifelong

A second entry point of the crate is the `Lifelong`

struct, which
can process a stream of planning requests. Each of those requests can ask
for new paths for a subset of agents, and those must avoid collisions with
the last planned paths for the other agents.

### §Genericity

Caboose allows to specify new environments by implementing the `TransitionSystem`

trait.
It reasons over:

- a set of states, implementing the
`State`

trait, that describe the state of an agent; - a set of actions that describe the possible moves of an agent, depending on its state;

and requires implementing a few functions that link them together, in particular:

`TransitionSystem::actions_from`

and`TransitionSystem::transition`

to describe the result of applying an action to a state;`TransitionSystem::transition_cost`

to describe the cost of applying an action to a state (i.e. the duration of the action);`TransitionSystem::conflict`

that checks whether two actions performed by two different agents lead to a collision.

You will probably also need to create a simple heuristic for your environment by implementing the `Heuristic`

trait.
This heuristic will be used by the search algorithm to guide the search, but should be simplistic
as it will only be used to guide the search for a more advanced heuristic given by `ReverseResumableAStar`

.

## Structs§

- Wrapper around an action that also contains the cost of the action.
- Input configuration for the Conflict-Based Search algorithm.
- Statistics of the Conflict-Based Search algorithm.
- An algorithm configuration to use to solve benchmark instances.
- Implementation of the Conflict-Based Search algorithm that plans collision-free paths for a set of agents.
- Differential heuristic built on top of heuristics dealing with time and durations.
- Input configuration for the Generalized Safe Interval Path Planning algorithm.
- Definition a weighted directed graph.
- Definition of a directed graph edge.
- A directed graph edge id.
- Definition of a directed graph node.
- A directed graph node id.
- Defines a time interval (start <= end).
- Input configuration for the Safe Interval Path Planning algorithm with landmarks.
- Statistics of the Safe Interval Path Planning algorithm with landmarks.
- A lifelong planner that supports requests for new tasks while other tasks are being executed. It uses Conflict-Based Search under the hood.
- The input configuration for a new planning request.
- Definition of a move in a transition system.
- Implementation of the Reverse Resumable A* algorithm that computes the shortest path between:
- Statistics of the Reverse Resumable A* algorithm.
- Implementation of the Safe Interval Path Planning algorithm that computes the optimal sequence of actions to complete a given task in a given transition system, while avoiding conflicts with other agents in the same environment.
- Implementation of Safe Interval Path Planning algorithm that supports landmarks (or positive constraints) to visit before aiming for the goal state.
- A heuristic that returns the time to connect two vertices of the graph in straight line.
- A state in the simple world, simply represented by a GraphNodeId.
- A world simply described by a directed weighted graph
- Input configuration for the Safe Interval Path Planning algorithm.
- State wrapper for the Safe Interval Path Planning algorithm that extends a given state definition with a safe interval.
- Statistics of the Safe Interval Path Planning algorithm.
- Task wrapper for the Safe Interval Path Planning algorithm that extends a given task definition with all SIPP states that correspong to it.
- Description of a solution to a search problem
- Definition of a task in a given transition system that can then be fed to a search algorithm.

## Traits§

- Definition of a callback that can be used to apply actions to a transition system.
- Defines a heuristic function that can be used by a search algorithm, for a given transition system and task.
- Trait to build heuristics on the fly.
- Trait to specify the minimum and maximum values of a type.
- Definition of a state in a transition system.
- Definition of a transition system that contains a set of states and actions, and transition functions that describe the result of any action applied to any state. The reverse transitions must also be described to allow using the reverse search as a heuristic.

## Functions§

- Builds a CBS algorithm and its configuration from the given files.
- Parse a configuration file.
- Parse the benchmark maps and scenarios from https://movingai.com/benchmarks/mapf/index.html
- Parse the benchmark maps and scenarios from https://movingai.com/benchmarks/mapf/index.html

## Type Aliases§

- A wrapper around f64 that implements Ord and LimitValues.
- The distance between two nodes in the graph.
- The (x,y) coordinates of a node in the graph.