AdditivePDBs.cs

using System.Collections.Generic;
using System.Diagnostics;
using System.IO;

namespace mapf
{
    public class AdditivePDBs : IHeuristicCalculator<WorldState>
    {
        List<PDB> PDBs; 

        /// <summary>
        /// The set of agents that are not covered by this set of pattern
        /// databases. This information is not used by this class or any of its
        /// related classes, but is simply precomputed as useful information for
        /// the caller (for example, if the caller wanted to add to our
        /// heuristic estimate).
        /// </summary>
        public SortedSet<uint> excludedAgents;

        /// <summary>
        /// Determines how many additive pattern databases to build and divides
        /// the agents among them, possibly leaving some agents out.
        /// </summary>
        /// <param name="pi">the problem instance to use</param>
        /// <param name="s">The root of the search tree. This is also expected
        /// to have context parameters such as agents' goal states.</param>
        public void build(ProblemInstance pi, WorldState s)
        {
            Debug.Write("Building database...");

             // As a simple rule, we'll simply take pairs of agents starting
             // with the first two, then the second two, etc.

            PDBs = new List<PDB>();
            if (s.allAgentsState.Length > 1)
            {
                for (uint i = 0; i < s.allAgentsState.Length - 1; i += 2)
                {
                     // Make a list of agents we want to include together in the
                     // next additive pattern database. We specify agents by
                     // their index into the WorldState.allAgentsState
                     // array.

                    List<uint> agentsToConsider = new List<uint>();
                    agentsToConsider.Add(i);
                    agentsToConsider.Add(i + 1);

                     // Create a new root search node where the state only
                     // includes a subset of the agents of the original search
                     // node. This is done by passing into the state copy
                     // constructor our list of important agents.

                    WorldState tws = new WorldState(s.allAgentsState, agentsToConsider);

                     // Initialize, build, and save the new pattern database.

                    EnumeratedPDB pdb = new EnumeratedPDB();
                    pdb.Init(pi, agentsToConsider);
                    pdb.build();
                    Debug.Write(".");
                    PDBs.Add(pdb);
                }
            }

             // Create single shortest path pattern database heuristics for the
             // remaining agents if we have any left over.

            if (s.allAgentsState.Length % 2 == 1)
            {
                SumIndividualCosts pdb = new SumIndividualCosts();
                List<uint> agentsToConsider = new List<uint>(1);
                agentsToConsider.Add((uint) s.allAgentsState.Length - 1);
                pdb.Init(pi, agentsToConsider);
                pdb.build();
                PDBs.Add(pdb);
            }

             // For informational purposes, we will set the number of agents
             // that aren't included in this set of pattern databases.

            excludedAgents = new SortedSet<uint>();

            Debug.WriteLine("done.");
        }

        /// <summary>
        /// Initializes the pattern database by storing references to the
        /// problem instance and also the subset of agents that the pattern
        /// database pertains to.
        /// </summary>
        /// <param name="pi">The problem instance.</param>
        /// <param name="vAgents">The agents that the pattern database should keep track of.</param>
        public virtual void Init(ProblemInstance pi, List<uint> vAgents) {}

        /// <summary>
        /// Simply returns the sum of each of the additive pattern database 
        /// heuristic estimates on the given state.
        /// </summary>
        /// <param name="s">The state.</param>
        /// <returns>The admissible heuristic value for the additive pattern
        /// databases.</returns>
        public uint h(WorldState s)
        {
            uint nHeuristicValue = 0;
            foreach (PDB p in PDBs)
            {
                nHeuristicValue += p.h(s);
            }
            return nHeuristicValue;
        }

        public bool empty()
        {
            return PDBs.Count == 0;
        }

        /// <summary>
        /// Prints header of statistics of a single run to the given output. 
        /// </summary>
        public void OutputStatisticsHeader(TextWriter output) { }

        /// <summary>
        /// Prints statistics of a single run to the given output.
        /// </summary>
        public void OutputStatistics(TextWriter output) { }

        public int NumStatsColumns {
            get
            {
                return 0;
            }
        }

        /// <summary>
        /// Clears statistics.
        /// </summary>
        public void ClearStatistics() { }

        public void ClearAccumulatedStatistics() { }
        public void AccumulateStatistics() { }
        public void OutputAccumulatedStatistics(TextWriter output) { }

        public override string ToString()
        {
            return this.GetName();
        }

        public string GetName()
        {
            return "Additive PDB";
        }
    }
}