Problem Solving with Domain-Independent Dynamic Programming: Theory and Practice (DIDP)

Domain-independent dynamic programming (DIDP) is a recently proposed framework for modeling combinatorial optimization problems using dynamic programming and solving them with a general purpose solver. Initial results show strong performance using a heuristic state-based search solver, thus demonstrating the success of problem solving approaches developed in Artificial Intelligence (AI) on problems traditionally studied in Operations Research (OR). This project seeks to develop the theory and practice of DIDP-based problem solving by characterizing DIDP from computational and knowledge representation perspectives; by understanding its relationship to the problem solving paradigms embodied in constraint programming, satisfiability, and AI planning; and by developing novel domain-independent heuristics for DIDP through the adaptation and extension of techniques from AI planning, state abstraction in OR, and decision diagram-based optimization.