This thesis deals with planning problems and Boolean satisfiability problems that represent major challenges for artificial intelligence.