A bug of ICTS + ID on warehouse map with 65 agents

To reproduce - run 'Debug'
OmriKaduri · Jan 11, 2020 · f138d79 · f138d79
1 parent bba40c1
commit f138d79
Show file tree

Hide file tree

Showing 186 changed files with 14,229 additions and 328 deletions.
diff --git a/.vs/mapf/v15/.suo b/.vs/mapf/v15/.suo
diff --git a/.vs/mapf/v15/Server/sqlite3/storage.ide b/.vs/mapf/v15/Server/sqlite3/storage.ide
diff --git a/.vs/mapf/v15/Server/sqlite3/storage.ide-shm b/.vs/mapf/v15/Server/sqlite3/storage.ide-shm
diff --git a/.vs/mapf/v15/Server/sqlite3/storage.ide-wal b/.vs/mapf/v15/Server/sqlite3/storage.ide-wal
diff --git a/Constants.cs b/Constants.cs
@@ -28,7 +28,7 @@ class Constants
         /// <summary>
         /// Max Consecutive failures before an algorithm is omitted from the list of tested algorithms
         /// </summary>
-        public const int MAX_FAIL_COUNT = 5;
+        public const int MAX_FAIL_COUNT = 1;
         /// <summary>
         /// This determines whether the ICTS should search for a solution with lowest conflicts for the ID framework
         /// </summary>

diff --git a/IndependenceDetection.cs b/IndependenceDetection.cs
@@ -44,6 +44,9 @@ class IndependenceDetection : ISolver
         private Dictionary<TimedMove, List<int>> conflictAvoidance;
         private int maxSolutionCostFound;
 
+        //Variables for ID + AS
+        private int subproblem_id;
+
         public IndependenceDetection(ISolver singleAgentSolver, ISolver groupSolver, Boolean withSelection = false)
         {
             this.singleAgentSolver = singleAgentSolver;
@@ -74,7 +77,10 @@ public void Setup(ProblemInstance instance, Run runner)
                 this.allGroups.AddLast(
                     new IndependenceDetectionAgentsGroup(
                         this.instance, new AgentState[1] { agentStartState },
-                        this.singleAgentSolver, this.groupSolver));
+                        this.singleAgentSolver, this.groupSolver, runner, 0));
+
+            this.subproblem_id = 0;
+
         }
 
         public virtual String GetName() {
@@ -277,7 +283,8 @@ public bool SimpleID(Run runner)
                     break;
                 allGroups.Remove(conflict.group1);
                 allGroups.Remove(conflict.group2);
-                IndependenceDetectionAgentsGroup compositeGroup = this.JoinGroups(conflict);
+                this.subproblem_id++;
+                IndependenceDetectionAgentsGroup compositeGroup = this.JoinGroups(conflict, this.subproblem_id);
 
                 // Solve composite group with A*
                 bool solved = compositeGroup.Solve(runner);
@@ -395,8 +402,8 @@ public bool ImprovedID(Run runner)
                     Debug.WriteLine($"Group2 plan before the merge: ");
                     conflict.group2.GetPlan().PrintPlan();
                 }
-
-                IndependenceDetectionAgentsGroup compositeGroup = this.JoinGroups(conflict);
+                this.subproblem_id++;
+                IndependenceDetectionAgentsGroup compositeGroup = this.JoinGroups(conflict, this.subproblem_id);
 
                 compositeGroup.instance.parameters[CONFLICT_AVOIDANCE] = conflictAvoidance;
 
@@ -438,9 +445,9 @@ public bool ImprovedID(Run runner)
         /// </summary>
         /// <param name="conflict">An object that describes the conflict</param>
         /// <returns>The composite group of agents</returns>
-        protected virtual IndependenceDetectionAgentsGroup JoinGroups(IndependenceDetectionConflict conflict)
+        protected virtual IndependenceDetectionAgentsGroup JoinGroups(IndependenceDetectionConflict conflict, int new_problem_id)
         {
-            return conflict.group1.Join(conflict.group2);
+            return conflict.group1.Join(conflict.group2, new_problem_id);
         }
 
         /// <summary>
@@ -538,7 +545,12 @@ class IndependenceDetectionAgentsGroup
         private MvcHeuristicForCbs mvc_for_cbs;
         private CBS cbsh;
 
-        public IndependenceDetectionAgentsGroup(ProblemInstance instance, AgentState[] allAgentsState, ISolver singleAgentSolver, ISolver groupSolver)
+
+        private Run runner;
+        private int subproblem_id;
+        private long timeToSolver;
+
+        public IndependenceDetectionAgentsGroup(ProblemInstance instance, AgentState[] allAgentsState, ISolver singleAgentSolver, ISolver groupSolver, Run runner, int subproblem_id)
         {
             this.allAgentsState = allAgentsState;
             this.instance = instance.Subproblem(allAgentsState);
@@ -575,7 +587,9 @@ public IndependenceDetectionAgentsGroup(ProblemInstance instance, AgentState[] a
                 useOldCost: false,
                 useCAT: true);
 
-
+            this.runner = runner;
+            this.subproblem_id = subproblem_id;
+            this.timeToSolver = 0;
         }
 
         /// <summary>
@@ -588,9 +602,14 @@ public bool Solve(Run runner)
             ISolver relevantSolver = this.groupSolver;
             if (this.allAgentsState.Length == 1)
                 relevantSolver = this.singleAgentSolver; // TODO: Consider using CBS's root trick to really get single agent paths fast. Though it won't respect illegal moves and such.
-
+
+            var watch = System.Diagnostics.Stopwatch.StartNew();
+
             relevantSolver.Setup(this.instance, runner);
             bool solved = relevantSolver.Solve();
+            watch.Stop();
+            this.timeToSolver = watch.ElapsedMilliseconds;
+
             this.solutionCost = relevantSolver.GetSolutionCost();
             if (solved == false)
                 return false;
@@ -601,6 +620,14 @@ public bool Solve(Run runner)
             this.generated = relevantSolver.GetGenerated();
             this.depthOfSolution = relevantSolver.GetSolutionDepth();
 
+            //TODO: Add print stastistics to different writer - writer of ID metadata
+
+            this.runner.OpenMetaIDResultsFile();
+            this.runner.PrintMetaIDProblemStatistics(this.instance);
+            OutputIDMetaStatistics(this.runner.metaIDResultsWriter);
+            this.runner.metaIDResultsWriter.WriteLine();
+            this.runner.metaIDResultsWriter.Flush();
+            this.runner.CloseMetaIDResultsFile();
             // Clear memory
             relevantSolver.Clear();
             return true;
@@ -703,14 +730,15 @@ public Plan GetPlan()
         /// </summary>
         /// <param name="other"></param>
         /// <returns>A new AgentsGroup object with the agents from both this and the other group</returns>
-        public IndependenceDetectionAgentsGroup Join(IndependenceDetectionAgentsGroup other)
+        public IndependenceDetectionAgentsGroup Join(IndependenceDetectionAgentsGroup other, int new_id)
         {
             AgentState[] joinedAgentStates = new AgentState[allAgentsState.Length + other.allAgentsState.Length];
             this.allAgentsState.CopyTo(joinedAgentStates, 0);
             other.allAgentsState.CopyTo(joinedAgentStates, this.allAgentsState.Length);
             Array.Sort(joinedAgentStates, (x, y) => x.agent.agentNum.CompareTo(y.agent.agentNum));  // Technically could be a merge
 
-            return new IndependenceDetectionAgentsGroup(this.instance, joinedAgentStates, this.singleAgentSolver, this.groupSolver);
+            return new IndependenceDetectionAgentsGroup(this.instance, joinedAgentStates, this.singleAgentSolver, this.groupSolver, this.runner,
+                new_id);
         }
 
         /// <summary>
@@ -765,8 +793,10 @@ public bool ReplanUnderConstraints(Plan plan, Run runner, Boolean withSelection)
             }
             else
             {
-                success = this.Solve(runner); 
+                success = this.Solve(runner);
             }
+
+
             this.instance.parameters.Remove(IndependenceDetection.ILLEGAL_MOVES_KEY);
             this.instance.parameters.Remove(IndependenceDetection.MAXIMUM_COST_KEY);
             if (success == false)
@@ -817,6 +847,19 @@ public void removeGroupFromCAT(Dictionary<TimedMove, List<int>> CAT)
             }
         }
 
+
+        /// <summary>
+        /// Prints statistics of every ID solver to the given output. 
+        /// </summary>
+        public void OutputIDMetaStatistics(TextWriter output)//, BsonDocument row)
+        {
+            //"GroupNumber","SolverUsed","SolverRuntime","GroupSize"
+            output.Write(this.subproblem_id + Run.RESULTS_DELIMITER);
+            output.Write(this.groupSolver.GetName() + Run.RESULTS_DELIMITER);
+            output.Write(this.timeToSolver + Run.RESULTS_DELIMITER);
+            output.Write(this.allAgentsState.Length + Run.RESULTS_DELIMITER);
+        }
+
         public override string ToString()
         {
             string ans = "group {";

diff --git a/ProblemInstance.cs b/ProblemInstance.cs
@@ -659,6 +659,7 @@ public static ProblemInstance ImportFromScenFile(string fileName)
 
                     if (resultsFileExisted == false)
                         runner.PrintResultsFileHeader();
+
                     runner.CloseResultsFile();
 
                     Console.WriteLine("Starting scen with {0} agents", i);

diff --git a/Program.cs b/Program.cs
@@ -13,6 +13,8 @@ namespace mapf
     class Program
     {
         public static string RESULTS_FILE_NAME = "Results.csv"; // Overridden by Main
+        public static string METAIDRESULTS_FILE_NAME = "ResultsMETAID.csv"; // Overridden by Main
+
         private static bool onlyReadInstances = false;
 
         /// <summary>
@@ -296,7 +298,7 @@ static void Main(string[] args)
             var resultsFileName = System.Guid.NewGuid();
             //Program.RESULTS_FILE_NAME = Process.GetCurrentProcess().ProcessName + ".csv";
             Program.RESULTS_FILE_NAME = resultsFileName + ".csv";
-
+            Program.METAIDRESULTS_FILE_NAME = resultsFileName + "METAID.csv";
             if (System.Diagnostics.Debugger.IsAttached)
             {
                 Constants.MAX_TIME = 300000;