PlanCritic: Formal Planning with Human Feedback
^††thanks: This project was funded by ONR Award No. N000142312840 and NSF Award No. 2021-67021-35329.

Interest in combining the flexibility of neural models with the speed and correctness of classical planners has been extensively studied. A number of early works focused on learning domains, with [5] using a deep-q network to translate existing instruction manuals into domains one-shot and [6] going a step further to learn STRIPS domains online with the help of an agent generating informative plan traces for training. With the advent of LLMs and their effectiveness at translation, particularly from natural language into (PDDL) [3], focus shifted towards verification, with [7] using an LLM-based agent to test the self-consistency of generated domains and make necessary repairs. The linguistic proficiency brought by LLMs allowed research into neurosymbolic planning architectures to branch out from domain learning as well. One approach explored is to generate a symbolic description of some aspect of the planning problem from natural language, such as [8] or [9], which would then be provided to an existing symbolic planner to produce a symbolic plan. Alternatively, the LLM could be queried for a symbolic plan directly from a natural language description of the problem, and which could then be symbolicly verified in an post-hoc manner [10]. Other works took advantage of the coding proficiency of larger models, with [11] using GPT-4 few-shot to generate programs which in turn created valid plans from a domain. These approaches, however, are all limited in their ability to explore the space of available plans due to their reliance on the LLM for variation.

Genetic algorithms (GAs) are frequently used to solve combinatorial optimization problems with large search spaces, drawing inspiration from the principles of natural selection and genetics [12]. By maintaining a population of potential solutions and stochastically improving them with respect to an objective function, these methods efficiently comb the search space without requiring that objective to be differentiable with respect to any of the candidates [13]. Genetic algorithms are also inherently parallelizable, enabling them to explore multiple regions of the search space simultaneously, increasing the likelihood that the global optimum is discovered [14]. Genetic algorithms have been successfully applied to tasks including production scheduling [15], route optimization [16], and resource allocation [17]. In robotic path planning, genetic algorithms help find collision-free paths that minimize travel time and energy consumption [18].

Reinforcement Learning with Human Feedback (RLHF) leverages human feedback to guide the learning process of a reinforcement learning agent, shaping the agent’s behavior in a way more aligned with human preferences than traditional reinforcement learning [19]. One prominent application of RLHF is in natural language processing tasks, where the goal is to align language models with human preferences and ethical guidelines. For instance, OpenAI’s GPT models have been fine-tuned using RLHF to ensure that their responses are not only relevant but also adhere to safety and ethical standards [20]. In the context of planning and decision-making, RLHF has been employed to refine the outputs of planning algorithms based on user feedback. For example, [21] demonstrated the use of RLHF in Atari games, where human feedback was used to train an agent to perform better than with traditional reward functions alone. Similarly, in robotic manipulation tasks, RLHF has been used to teach robots complex behaviors that are difficult to specify through conventional reward functions [22].

To ensure performance in highly dynamic environments, we focused on optimizing a plan with respect to user feedback as opposed to generating entire problem files. This enabled PlanCritic to rapidly adapt the way a plan is executed without the risk of derailing the ground-truth end goal. To achieve this, for any given problem $\mathcal{P}^{i}$ we treat the classical planner $\rho$ as a model parameterized by a set of constraints $\mathcal{C}^{i}=\{{c^{i}}_{1},{c^{i}}_{2},...,{c^{i}}_{n}\}$ specified in PDDL such that:

Where $\mathcal{S}$ is the resulting set of steps constituting the plan. In order to optimize this model with respect to user feedback specified in natural language, we followed RLHF and trained a reward model to score plans generated by the planning model. Taking the set of user feedback to be $\mathcal{F}=\{f_{1},f_{2},...,f_{n}\}$, we define reward model $\nu$ as follows:

We assume that the symbolic planner used is deterministic. Thus, each $\mathcal{C}^{i}$ corresponds to only one $\mathcal{S}$, enabling us to use the reward model to uniquely determine the adherence of a constraint set to the feedback provided by the user.

While RLHF approaches typically use a gradient-based optimizer to tune their initial model with respect to their score model, the use of an external symbolic planner to generate plans makes this gradient-based approaches infeasible. To address this concern we used a genetic algorithm, treating different $\mathcal{C}^{i}$ for problem $i$ as individuals in the GA’s population. Since we used PDDL, we can rigidly define a constraint as:

Defining constraints in this way gives three axes of change by which to mutate a constraint without entirely replacing it: negation, changing its state-trajectory constraint $t$, and modifying one of the arguments of its predicate $p$. In addition to constraint-level mutations, we define adding and removing constraints as rare individual-level mutations to ensure more rapid exploration and prevent getting stuck in local minima. Algorithm 1 describes the mutation operation used by the GA.

We describe the crossover operation in Algorithm 2. The crossover operation generates a child by selecting a random crossover point, and combining the constraints before the crossover point from one parent with the constraints after the crossover point from the other parent.

To assess the fitness of the individuals in the population, we use the LSTM-based reward model $\nu$ described in the previous section.

To both maximize the information available to the reward model and ensure that the genetic algorithm starts its optimization in the neighborhood of the actual solution, we implemented the system architecture described in Fig. 1 as an interface between the user and the GA-based planner. After the user gives their preferences, GPT-4 is utilized to translate these preferences into symbolically grounded natural language constrains we term mid-level goals. Examples are given in Table I. These mid-level goals are then used by GPT-4 to generate an initial candidate $\mathcal{C}$. This initial constraint set is duplicated to produce the initial population of candidate constraints for the GA, and these duplicates are mutated to ensure diversity. To prevent issues caused by GPT-4 returning invalid PDDL constraints, we developed a parser which takes in the model’s output and corrects syntactical errors with the most likely valid replacement as determined by Gestalt pattern matching [24]. Once planning is complete, GPT-4 summarizes the result of planning and each of the plan steps and returns the outcome to the user.