this is for holding javascript data
guni edited sectionReducing_Opti.tex
over 9 years ago
Commit id: 28e14fb81faa26a81f9a2921b143c99f1a30fe15
deletions | additions
diff --git a/sectionReducing_Opti.tex b/sectionReducing_Opti.tex
index 51da9f6..2c3892d 100644
--- a/sectionReducing_Opti.tex
+++ b/sectionReducing_Opti.tex
...
\section{Reducing MAPF to the CA Problem}
Different CA solvers provide different
gurentees, guarantees, e.g. social
whelfer, welfare, truthfulness, prioritized agents and more. Solving MAPF using a CA solver provides these
guarntees guarantees for MAPF.
A solution for the MAPF problem is composed from a set of paths, one per agent. Each single agent path is composed from a set of coordinates, i.e. \{vertex, time step\} pairs. The MAPF problem can be easily reduced to CA when every
coordinanet coordinate is
considerd considered an item and every path a
bondle. bundle.
CA is defined only on a finite set of items. Consequently only a finite number of coordinates can be taken into account. This calls for a bound on the number of time steps required until all agents reach their goal. It was proven that a solvable MAPF instance can be solved in less than $|V|^3$ time steps \cite{kornhauser1984coordinating}. Using this bound allows us to consider a finite number of items, $|V|^3 \times |V| = |V|^4$.
In CA each agent $k_i$, is required to provide a utility evaluation for any boundle $b$, this utility is used to detrmine the maximal price that agent $k_i$ is willing to pay for $b$.
CA is defined only on a finite set of items. Consequently only a finite number of coordinates can be taken into account. This calls for a bound on the number of time steps required until all agents reach thier goal. It was proven that a solvable MAPF instance can be solved in less than $|V|^3$ time steps \cite{kornhauser1984coordinating}