Incorrect ParallelIDAstar Result When C*<workDepth

[lior8]

The following program shows a case where C=2, but PIDA returns 12.

#include <cinttypes>
#include <iostream>
#include "MNPuzzle.h"
#include "ParallelIDAStar.h"

int main(int argc, char *argv[]) {
    MNPuzzle<4, 4> env;
    MNPuzzleState<4, 4> start;
    MNPuzzleState<4, 4> goal;
    env.ApplyAction(start, kRight);
    env.ApplyAction(start, kRight);
    std::cout << "Start:" << start << std::endl;
    std::cout << "Goal: " << goal << std::endl;
    ParallelIDAStar<MNPuzzle<4,4>, MNPuzzleState<4,4>, slideDir> ida;
    std::vector<slideDir> solution;
    ida.GetPath(&env, start, goal, solution);
    std::cout << "Optimal cost: " << env.GetPathLength(start, solution) << std::endl;
}

Gives the following output:

Op order: Right Left Down Up                     
Start:(4x4)1 2 0 3 4 5 6 7 8 9 10 11 12 13 14 15 
Goal: (4x4)0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
66 pieces of work generated
Starting iteration with bound 2.000000; 56 expanded, 176 generated
Starting iteration with bound 4.000000; 56 expanded, 176 generated
Starting iteration with bound 6.000000; 56 expanded, 176 generated
Starting iteration with bound 8.000000; 56 expanded, 176 generated
Starting iteration with bound 10.000000; 61 expanded, 193 generated
Starting iteration with bound 12.000000; 101 expanded, 313 generated
Optimal cost: 12

This is likely because there is no goal check in GenerateWork() (or later in StartThreadedIteration()).

[lior8]

Since the generation is a limited DFS, even if there is a termination condition within there, it can prove problematic as it might be suboptimal. Instead I suggest thinking of a new way to generate work which generates the level in sequential manner until it hits some critical mass of work which can then be parallelized.