This paper describes a theoretical framework for a system for menu planning and recipe design, which builds on a previously developed AI system for problem solving that proceeds, in large part, through categorization. The task addressed in this framework is the retrieval and creation of recipes and menus that are consistent with stated constraints, and that are ordered in their presentation by factors such as projected value, novelty, and unexpectedness.
This paper describes how a library of recipes, meals, and menus can be used for
reuse, reconfiguration, and remixing by human and/or AI chefs and cooks. This work
is building on research from machine learning and AI on problem solving through
categorization (in the domain of math problem solving), as well as prior research on
AI for cooking
The particular task addressed in this framework is the identification of recipes and menus through exploitation and exploration processes of retrieval and creation, respectively. Recipes are consistent with stated constraints, and recipes and menus can be ranked by projected value (e.g., taste, nutrition), novelty, and unexpectedness.
Categorization and problem solving research that is relevant to culinary creation
stems from a knowledge-rich form of machine learning called explanation-based
learning
A limitation of the explanation-based approach is that it requires a domain theory of inference rules, which are often assumed to be “perfect”. Thus, explanation-based reasoning is often regarded as deductive. But the same explanation-based machinery can use inference rules that do not yield deductively-sound conclusions, so long as those rules are formatted consistent with system specification. So while the need for a domain theory is a legitimate limitation, the domain theory can be inconsistent, which is particularly important in the recipe design setting. 2.1
Yoo and Fisher (1991) and Fisher and Yoo (1993), in their system EXOR
(Explanation Organizer), combined explanation-based learning with more traditional forms
of inductive machine learning, such as generalization
The effect of EXOR is to restructure the AND-OR search that is common in problem solving, from a search space in which OR and AND nodes are interleaved and alternating, to a single OR tree of partial explanations (aka problem solving traces). In turn, each explanation (aka a node in the OR tree) is an AND tree that represents a (partial) solution. Partial explanations accumulate details as the OR tree is traversed from root to leaf, where the root is the empty design (aka explanation or solution) and a leaf is a fully-realized design in the form of a complete AND tree (though EXOR uses pruning mechanisms, so that leaves are often only partial solutions or designs).
This single OR tree (of AND trees) has the advantage that it can be more easily indexed for purposes of speeding traversal in search of past knowledge that is most relevant to a current problem. Indices that correspond to features of the problem statement (aka surface features), or features that are inferred from those features (aka deep features) are used to direct the categorization process based on a best match between features of the problem being solved and solutions in the hierarchy.
In EXOR, cost effective features for indexing are identified that optimize a tradeoff
between the cost of inferring the presence of the feature in the current problem, and
the search through the space of AND tree designs that is saved by using the feature as
an index into the OR tree. These indexing features are EXOR’s implementation of a
boundary of operationality
With the abstraction hierarchy (OR tree) over problem solving traces at varying levels of abstraction, and indices to guide search, EXOR solves a new problem by traversing the abstraction hierarchy in a meaningful way, guided by features of the problem, “accumulating” a single complete solution as it does so. However, traversing an EXOR tree is still an AND/OR search, but one that is typically more efficient than a search is a less structured space. Unlike categorization in other paradigms, such as classification with a decision tree, categorization in an EXOR-induced tree is not strictly deterministic, but rather backtracking happens if and when there is a contradiction between what is known about a current problem and a partial solution.
Importantly, if there is no current complete solution in the EXOR tree that solves a
problem without conflicts, then EXOR reverts to searching background knowledge
for a way to complete an existing partial solution. Thus, EXOR can expand its
hierarchy of solution traces as needed, through a process of categorization-centric problem
solving, so long as it has a complete (even if inconsistent) domain theory. In
casebased terms, the role of cases can be thought of as providing search control
knowledge
Instead of AND-tree-structured problem solutions in a domain of algebra story problems, which was EXOR’s original test domain, this paper describes a proposed adaptation of EXOR that organizes and creates AND-tree-structured culinary constructs, with annotations in these constructs that represent assemblage processes of mixing, cooking, and presentation. 3.1
In the cooking domain particularly, EXOR can be viewed as combining aspects of
compositional and generative adaptation used by other culinary assistants
Research by Gaillard, Lieber, & Nauer (2015) also uses an isa-hierarchy of ingredients to guide search for similar cases, as well as a concept lattice, which is a graph generalization of an EXOR-like abstraction hierarchy.
If there is a niche for an EXOR-like recipe assistant relative to these and other
efforts, it is perhaps in the form of abstractions, and selectivity with which EXOR
creates and maintains abstractions. It also is the case that EXOR predates much of the
other work, and appears to still have novel contributions to make on generalizing
cases, cost-effective indexing of cases, and “optimal” levels of generalization, in the
cooking domain and otherwise. This last concept of “optimal” levels of
generalization, or basic levels, supposes that there is an abstraction level of problem solving that
provides the “most bang for the buck”
A portion of a potentially very large hierarchy of recipes is shown in figure 1. The paths in the hierarchy (OR tree) that are enumerated from root to leaves show how each child of a node (an AND tree) expand the AND tree of its parent node, and how different children of a common parent expand the parent in different ways. In addition to the abstraction over ingredient-based AND-trees that are depicted in the figure, there can be annotations of each AND tree that reflect processing guidelines for preparing recipes by mixing, cooking, and presenting. These annotations indicate processes that could be carried out by multiple agents (e.g., in a restaurant kitchen), or just one agent, with asynchronous processing allowed, but under some synchronizing constraints (e.g., “mix the dry ingredients” presumably in any order, then “stir in the eggs and milk”). In any case, we desire a representation of recipes that include • • • • the ingredient-based AND-trees; the varying quantities on ingredients; context information, such as who commissioned a meal; and the recipe’s asynchronous procedural guidelines for assembling dishes (e.g., mixing ingredients and cooking), under constraints.
The inclusion of context features, such as the “Chancellor commissioned the meal” and the inferences that follow from that, may be a novel functionality.
As noted earlier, the ingredient-based AND trees are similar to nodes of a concept lattice used by Gaillard, Lieber, & Nauer (2015).
The workflow representations of Müller and Bergmann (2014, 2015) are an existing formalism for representing the process knowledge in cooking, as well as the ingredient knowledge. At a minimum, it will be an interesting exercise to adapt the workflow representation to EXOR-style hierarchies, which appear to generalize the data node constructs in Müller and Bergmann.
The TAEMS framework
A recipe creation agent can use an augmented abstraction hierarchy of recipes in a variety of ways. If a set of constraints is specified, such as a fixed set of required ingredients (e.g., think the TV show, Chopped), much like a problem statement in EXOR’s prior life, then the recipe creation agent can act much like EXOR, through categorization-centric problem solving. The goal in the cooking setting is any recipe or menu that satisfies the constraints (e.g., set of required ingredients). Of course, many recipes may satisfy the goal conditions, so it is desirable to rank minimallysatisfactory recipes by factors such as value (e.g., taste, nutrition, carbon footprint), novelty, and unexpectedness.
To review, the recipe creation agent would find a path in the hierarchy that is
suggested by cost-effective indexing features, but which also satisfies the constraints
(e.g., of required ingredients), and reverting to less-structured domain knowledge, as
necessary, to complete partial recipes found through categorization. Domain
knowledge in this setting would include transformation operators, like those
specifying that one ingredient (e.g., apple sauce) might be a good substitute for another (e.g.,
butter) under particular circumstances (e.g., baking), and that one cooking method can
be substituted for another
Constraints other than requisite ingredients that can be used to prune the search of the recipe hierarchy include ingredients to be excluded, such as refined sugar, gluten, tree nuts, and other health-motivated exclusions. In the culinary domain, cost effective features that might direct categorization could be ingredients that complement ingredients in a partial recipe or the identity of a special patron for which the recipe is being created. Figure 1 illustrates that chocolate is introduced as an ingredient at one node because of a known customer preference that is encoded as an inference rule. Elsewhere in the hierarchy, “patron=Chancellor” is inferred due to another rule, and this feature will bias (or hard constrain) categorization down some sub-trees and not others. The nature of the domain theory can vary from generalized knowledge (e.g., about frequent ingredient substitutions), to highly specific context knowledge about the individual patron preferences and restrictions.
More generally, instead of searching the abstraction hierarchy for a single recipe
solution, search can continue to find multiple solutions, perhaps for anytime
motivations (e.g., again, think Chopped), and/or to uncover a number candidate recipes that
can be assessed in terms of novelty, utility, and surprise relative to the recipes that are
in the existing recipe repository
Traversing the recipe hierarchy can be extended to search for multiple recipes that are complementary, which is important in meal and menu creation. A restaurant or catered meal is composed of a combination of dishes that are complementary, where each dish is created through a recipe. A meal shares the desire for complementarity among its components with a recipe, albeit with more loosely-coupled procedures for the assemblage of the former than the latter. A menu for a catered buffet also includes several-to-many dishes, each of which is again created through a recipe. While there is attention to complementarity in a buffet menu, there is greater flexibility in how patrons sample and assemble their individual meals, and so the complementarity (or coupling) between any pairs (or combinations more generally) of particular dishes is less. The complementarity between meals in a non-buffet restaurant menu is more loosely coupled still, driven more by resources of the kitchen than customers, very few of whom would order more than one meal at a sitting.
In sum, dishes/recipes are composed of atomic foods and/or composite sub-recipes; meals are composed of dishes/recipes; and menus are composed of dishes as well, with or without intervening meal constructs. It is tempting to treat meal and menu planning as special cases of “recipes”, but with differing rules and guidelines for composition – ones that reflect different demands for complementarity, both of taste and nutrition. To some extent, this theoretical union may be productive. 3.5
Specificity of recipes provides constraints, as do (low-level) component composite foods (e.g., an Alfredo sauce) that are available for use in larger recipes. These lowest level composite constructs may correspond to streamlets (Müller and Bergmann (2014, 2015). Between high-level recipe template and low-level components, are midlevel recipe-design elements, which if fully fleshed out, give no room for creativity, and if not sufficiently fleshed out, recipe design may default to design from scratch. An issue that should be addressed is related to the previously raised idea of boundaries of operationally, but rather than being concerned with increasing the likelihood of beneficial reuse for problem solving speed up, we want optimal (or basic) levels of abstraction for purposes of creative recipe design, with a particular eye towards designs that are novel, utile, and surprising.
In terms of the well-known and pervasive exploitation-exploration tradeoff, EXOR was heavily biased towards exploitation. However, rather than resorting to domain theory search only when fully-specified recipes fail to satisfy all constraints, in the recipe creation agent, a relaxed version of categorization-centric problem solving would appeal to domain theory search at intermediate nodes, more proactively by deviating from established paths.
An important issue in this regard is the criteria that the agent should use to explore
by deviating into a less constrained domain theory search even before it has exhausted
all options to exploit. If we were still in the classic problem solving realm, our
temptation to venture away from established chunks or macros
The paper describes computational cognitive strategies that underlie a potential
recipe creation agent, based on earlier work on categorization and problem solving,
and thanks to reviewers, by prior research on AI cooking assistants. While this work
is clearly related to case-based approaches that seem dominant in the cooking domain,
the work on generalization towards basic levels of problem solving
There are very interesting issues that are currently underdeveloped, which would be desirable to talk through with workshop participants. How can ingredient ANDtrees be best augmented with the procedural information (e.g. with TAEMS) that are an important aspect of recipes, be folded into the generalization operations of an EXOR-like recipe creation agent? What are ideal criteria for managing the exploration and exploitation tradeoff in search for creative recipes, meals, and menus? What is the potential advantage of proactive case merging – aka generalization – to improve (or not) recipe design?
Three very helpful reviews pointed to a substantial body of related work.