LexiCon: a Benchmark for Planning under Temporal Constraints in Natural Language
Periklis Mantenoglou, RISHI HAZRA, Pedro Zuidberg Dos Martires, Luc De Raedt
Owing to their reasoning capabilities, large language models (LLMs) have been used to perform planning with natural language. However, LLMs have largely been tested on unconstrained planning domains. In order to deploy them in real-world settings where adherence to constraints, in particular safety constraints, is critical, we need to evaluate their performance on constrained planning tasks. We introduce LEXICON — a natural language-based (LEXI) constrained (CON) planning benchmark, consisting of a suite of environments, that can be used to evaluate in a principled fashion the planning capabilities of LLMs. The core idea behind LEXICON is to take existing planning environments and impose temporal constraints on the states. These constrained problems are then translated into natural language and given to an LLM to solve. A key feature of LEXICON is its extensibility. That is, the set of supported environments can be extended with new (unconstrained) environment generators, for which temporal constraints are constructed automatically. This renders LEXICON future-proof: the hardness of the generated planning problems can be increased as the planning capabilities of LLMs improve. Our experiments reveal that the performance of state-of-the-art LLMs, including reasoning models like o3 and R1, dramatically deteriorates as the degree of constrainedness of the planning tasks increases.