=Paper=
{{Paper
|id=Vol-2028/paper26
|storemode=property
|title=Cooking Made Easy: On a Novel Approach to Complexity-Aware Recipe Generation
|pdfUrl=https://ceur-ws.org/Vol-2028/paper26.pdf
|volume=Vol-2028
|authors=Gilbert Müller,Ralph Bergmann
|dblpUrl=https://dblp.org/rec/conf/iccbr/MullerB17
}}
==Cooking Made Easy: On a Novel Approach to Complexity-Aware Recipe Generation==
https://ceur-ws.org/Vol-2028/paper26.pdf
229
Cooking made easy: On a novel approach to
complexity-aware recipe generation
Gilbert Müller and Ralph Bergmann
Business Information Systems II
University of Trier
54286 Trier, Germany
[muellerg][bergmann]@uni-trier.de
http://www.wi2.uni-trier.de
Abstract. This paper presents an approach to generate easy-to-prepare cooking
recipes represented as workflows. A novel complexity-aware generation approach
is described that considers various aspects such as preparation time, number of
ingredients, and difficulty of preparation to optimize the complexity of the recipe.
Based on a user query specifying the desired and undesired ingredients or prepa-
ration steps, easy-to-prepare dishes are generated automatically.
Keywords: workflow complexity, workflow adaptation, cooking, process-oriented
case based reasoning
1 Introduction
Nowadays, an increasing amount of amateur chefs become fascinated by the world of
cooking. Traditional cooking websites support these chefs in finding suitable cooking
recipes. However, the recipes need to match several criteria, which sometimes require
recipes to be adapted to the individual demands of the user. These demands include
contained ingredients, required preparation tools, or dietary restrictions. Thus, several
novel approaches have been presented aiming at supporting the user beyond traditional
recipe search (e.g., [5,7,3,6]). In certain situations, amateur chefs may prefer easy-to-
prepare cooking recipes with a short preparation time, low required cooking skills, or a
small amount of ingredients for a variety of reasons.
In this paper we will describe a novel approach that automatically constructs indi-
vidual and easy-to-prepare cooking recipes based on ingredients and preparation steps
specified as desired or undesired. The approach is based on our CookingCAKE frame-
work [10], which will be extended by a new complexity-aware recipe generation. The
remainder of this paper is organized as follows: The next section presents the founda-
tions of the CookingCAKE framework. Then, we introduce a complexity assessment
for cooking recipes represented as workflows, which will be applied during Cook-
ingCAKE’s recipe generation. Finally, we present our prototypical implementation for
competing in the Easy Steps Challenge of the Computer Cooking Contest.
Copyright © 2017 for this paper by its authors. Copying permitted for private and
academic purpose. In Proceedings of the ICCBR 2017 Workshops. Trondheim, Norway
230
2 CookingCAKE
CookingCAKE constructs individual cooking recipes represented as workflows by means
of Process-oriented Case-based Reasoning [8]. In a nutshell, CookingCAKE selects the
best matching cooking workflow from the workflow repository (case base) and subse-
quently adapts it according to a query specified by the user.
2.1 Cooking Workflows
In our approach a cooking recipe is represented as a workflow describing the process to
prepare a particular dish [13] (see Fig. 1). A cooking workflow W = (N, E) consists
of nodes N = N T ∪ N D and edges E = E C ∪ E D . Nodes of the workflow represent
preparation steps N T (also called tasks) or ingredients N D (also called data nodes).
The execution order of preparation steps is defined by control-flow edges EC ⊆ N T ×
N T and the consumption or production of an ingredient is specified by data-flow edges
ED ⊆ (N T × N D ) ∪ (N D × N T ). Furthermore, we enforce that the workflow is
executable, which means here that it consists of a single sequence of tasks such that
each task t ∈ N T consumes (∃d ∈ N D : (d, t) ∈ E D ) and produces (i.e., ∃d ∈ N D :
(t, d) ∈ E D ) at least one ingredient, respectively. An example cooking workflow for a
sandwich recipe is illustrated in Fig. 1.
2.2 Ingredient and Preparation Step Similarity
To support retrieval and adaptation of workflows, the individual workflow elements
are annotated with ontological information resulting in a semantic workflow [2]. Cook-
ingCAKE uses a taxonomy of ingredients to define the semantics of data items and a
taxonomy of preparation steps to define the semantics of tasks. These taxonomies are
employed for the similarity assessment between tasks and data items. An example in-
gredient taxonomy is given in Figure 2. A taxonomy is ordered by terms that are either
a generalization or a specialization of a specific other term within the taxonomy, i.e., an
inner node represents a generalized term that stands for the set of most specific terms
below it. For example, the generalized term vegetarian in the illustrated taxonomy
italian sandwich
mayonaise mustard sauce
seasoning dish
grate slice mix add spread add layer sprinkle bake
baguette salami
cucumber
cheese
data-flow edge control-flow edge control-flow node data node task node
Fig. 1. Example of a block-oriented cooking workflow
231
stands for the set {potatoes, rice, noodles, . . .}. Inner nodes in generalized workflows
represent that an arbitrary ingredient from the set of its specializations can be chosen.
ingredients
0.01
vegeterian non vegeterian
0.1 0.1
side dish vegetables liquids seafood meat 0.6
...
0.5 0.6 0.3 0.7
...
...
...
potatoes rice noodles beef pork chicken turkey
Fig. 2. Example of an ingredient taxonomy
In our previous work, we developed a semantic similarity measure for workflows
that enables the similarity assessment of a case workflow Wc w.r.t a query workflow
Wq [2], i.e. sim(Wc , Wq ). Each query workflow element xq ∈ Wq is mapped by the
function m : Wq → Wc to an element of the case workflow xc ∈ Wc , i.e., xc = m(xq ).
The mapping is used to estimate the similarity between the two workflow elements uti-
lizing the taxonomy, i.e., sim(xq , xc ). The similarity of preparation steps or ingredients
reflects the closeness in the taxonomy and further regards the level of the taxonomic el-
ements. In general, the similarity is defined by the attached similarity value of the least
common ancestor, e.g., sim(beef, pork) = 0.6. If a more general query element such
as meat is compared with a specific element below it, such as pork, the similarity value
is 1. This ensures that if the query asks for a recipe containing meat, any recipe work-
flow containing any kind of meat is considered highly similar. All the similarity values
of the mappings are then aggregated to estimate an overall workflow similarity.
2.3 Workflow Query Language
CookingCAKE uses the query language POQL [12] to capture desired and undesired
ingredients or preparation steps of a cooking workflow as query q. The ability to spec-
ify preparation steps is useful as certain tools might not be available or their usage is
desired (e.g., oven). Let qd = {x1 , . . . , xn } be a set of desired ingredients or prepa-
ration steps and qu = {y1 , . . . , yn } be a set of undesired ingredients or preparation
steps, respectively. A query q is then defined as (x1 ∧ . . . ∧ x2 ) ∧ ¬y1 ∧ . . . ∧ ¬yn .
POQL further enables the specification of generalized terms, i.e., if a vegetarian dish
is desired, this can be defined by ¬meat. The query q is used to guide retrieval, i.e.,
to search for a workflow which at best contains all desired elements but no undesired
element. Based on the query q the not matching elements can be identified, enabling
to determine the elements to be deleted or added to the retrieved workflow during the
subsequent adaptation stage. The query fulfillment of a workflow W for a query q is
defined as the similarity between the desired ingredients/preparation steps as well as the
workflow W and the number of undesired ingredients/preparation steps not contained
in W according to the workflow similarity (see Sec. 2.2) in relation to the size of the
query (see Formula 1).
232
P
x∈qd sim(x, m(x)) + |{y ∈ qu |sim(y, m(y)) 6= 1}|
QF (q, W ) = (1)
|qd | + |qu |
Consequently, similar desired ingredients or preparation steps increase the query
fulfillment, while matching undesired ingredients or preparation steps reduce the query
fulfillment between the POQL query and the workflow.
2.4 Recipe Construction
Based on the defined POQL query, CookingCAKE constructs a workflow automati-
cally by retrieving the best matching workflow from the repository (case base) and
adapting it according to the query fulfilment. Consequently, the adaptation process of
CookingCAKE aims at adding missing desired ingredients/preparation steps and at re-
moving undesired contained ingredients/preparation steps. In a nutshell, the adaptation
process uses three different adaptation methods that are subsequently executed. First,
entire components of the cooking dish such as the sandwich sauce or sandwich topping
are replaced by matching components from other recipes [9]. Next, adaptation is per-
formed by use of operators that define possible and valid modifications on the cooking
workflows. Finally, the cooking recipes are adapted by replacing single ingredients and
preparation steps by means of the specified taxonomy, assuming that similar terms can
most likely be replaced with each other [11]. In all approaches, adaptation of a work-
α α α
flow is performed by chaining several adaptation steps W →1 W1 →2 . . . →n Wn = W 0 ,
which iteratively transforms the retrieved workflow W towards an adapted workflow
W 0 . This process solves an optimization problem aiming at maximizing the specified
criterion, which is so far implemented by the query fulfillment. Thus, the recipe con-
struction is a search process with the goal to achieve an adapted workflow with the
highest query fulfillment possible. The overall recipe construction process ensures the
syntactical correctness of the workflows, i.e., that the workflows are executable. More
detailed information on the construction process of CookingCAKE can be found in the
corresponding publication [10].
In the next section, we introduce a new criterion for the retrieval and adaptation
process that considers the complexity of workflows. Thus, retrieval as well as the adap-
tation become complexity-aware and aim at optimizing the constructed workflow with
regard to the new defined criterion during recipe construction.
3 Complexity Assessment
In the literature various approaches to asses the complexity of workflows exist (see
[4]). In this approach, we rather focus on a domain-specific complexity measure for
cooking workflows. During recipe construction, this complexity criterion is considered
to generate easy-to-prepare recipes automatically. We assume that the complexity of a
recipe is less focused on one single feature, but is composed by several criteria. Thus,
we deploy a complexity measure that covers five different indicators for determining
the complexity of the recipe (see Table 1).
233
Table 1. complexity criteria
critera description criteria measure
|N D |
number of ingredients max{|N1D |,...,|Nn
D |}
|N T |
number of preparation steps max{|N1T |,...,|Nn
T |}
T
|
complexity of ingredient processing 1 − 2·|N
|E D |
P
taskComplexity(t)
t∈N T
complexity of preparation steps |N T |
preparationT ime(W )
duration of preparation max{preparationT ime(W1 ),...,preparationT ime(Wn )}
The first two criteria measure basic complexity properties, i.e., the number of prepa-
ration steps as well as the number of ingredients in the particular cooking workflow
W = (N, E). Both measures are normalized by the highest amount of ingredients
or preparation steps contained in the workflows from the workflow repository. Conse-
quently, cooking workflows with more ingredients or more preparation steps are as-
sumed to be more complex. Furthermore, the complexity of preparation steps as well
as the complexity of ingredient processing represent two additional complexity crite-
ria. The complexity measure for ingredient processing considers the average amount
of ingredients consumed and produced by the preparation steps, which assigns a high
complexity value to those workflows in which the preparation steps N T consume and
produce a large amount of ingredients1 E D . In contrast, for computing the complexity of
preparation steps each task t in the taxonomy (see Sec. 2.2) is annotated by an estimated
task complexity value taskComplexity(t) ∈ [0, 1]. As an example, the preparation
step blanche is considered to be more complex than the preparation step mix. The crite-
rion is then defined as the average complexity of the preparation steps in the workflow
W . Finally, the duration for preparing a particular dish is also a factor affecting the com-
plexity. Therefor, also approximated execution times taskP reparationT ime(t) ∈ N
are annotated to each task t in the taxonomy. Here, for example, baking is annotated
by a long execution time, while season is considered as a rather short preparation step.
The duration of preparation for a workflow W is then heuristically measured by ag-
gregating the execution times of the preparation steps, i.e., preparationT ime(W ) =
P
t∈N T taskP reparationT ime(t). To assess the corresponding complexity, this value
is normalized in relation to the workflows from the repository as defined in Table 1.
Each of these five complexity measures determines a complexity value within the
interval [0, 1]. Based on these measures, we constructed an overall complexity measure
complexity(W ) → [0, 5] which adds up all complexity criteria to a single value. The
1
Please note that each task in a workflow consumes and produces at least one ingredient, re-
spectively (see Sec. 2.1)
234
overall complexity measure specifies the corresponding difficulty level of the recipe
preparation and distinguishes between very easy ([0, 1[), easy ([1, 2[), medium ([2, 3[),
difficult ([3, 4[) and very difficult ([4, 5]).
QFcomplexity (q, W ) = α · QF (q, W ) + (1 − α) · (1 − complexity(W )/5) (2)
Based on this overall complexity measure, we defined a new complexity-aware
query fulfilment measure QFcomplexity (q, W ) → [0, 1] (see Eq. 2) for the retrieval and
adaptation process. It replaces the query fulfillment measure specified in formula 1,
thus considering complexity as well. Both criteria may be weighted by a parameter
α ∈ [0, 1]. The workflow construction process of CookingCAKE as described in Sec-
tion 2.4 then aims at optimizing the constructed workflow with regard to this new crite-
rion. Please note that this is a multi-objective optimization problem and thus the adap-
tation may not be able to maximize the query fulfillment and to reduce the complexity
of the workflow at the same time.
4 Computer Cooking Contest: Easy steps challenge
We created a new user interface for the CookingCAKE system in order to address the
Easy Steps Challenge of the Computer Cooking Contest, which applies the previously
described complexity assessment. A running prototype of the implementation is avail-
able under (http://cookingCAKE.wi2.uni-trier.de/complexity), which uses a workflow
repository of 61 sandwich recipes manually modelled from various Internet sources
(e.g., sandwich recipes on WikiTaaable [1]2 ). The employed taxonomies of preparation
steps and ingredients (see Sec. 2.2) are based on the WikiTaaable ontology and were
manually annotated with similarity, preparation time, and task complexity values.
The query of CookingCAKE involves desired and undesired ingredients as well as
desired and undesired preparation steps. An example query ( http://cookingCAKE.wi2.
uni-trier.de/complexity?d=cherry%20tomato|salmon&u=cheese), generates a salmon and
cherry tomato recipe without using any kind of cheese. CookingCAKE then selects
the best matching workflow from the repository and subsequently adapts it according to
the novel criterion QFcomplexity (q, W ). Thus, the system tries to maximize the query
fulfilment on the one hand and on the other hand aims at reducing the complexity of the
workflow to generate an appropriate easy-to-prepare recipe for an amateur chef. The
result page of the novel CookingCAKE interface also displays the estimated difficulty
of preparation, the computed duration time as well as the single complexity values (see
Sec. 3) for the constructed recipe.
To evaluate our new complexity-aware approach for recipe construction, we gener-
ated 61 queries automatically. More precisely, for each workflow W , a corresponding
query was constructed by selecting the most similar workflow W 0 from the repository
and by determining the difference between the two workflows. The constructed query
considers workflow elements as desired that are only contained in the workflow W
while the elements only contained in workflow W 0 are considered as undesired. At
2
http://wikitaaable.loria.fr
235
most 4 randomly selected ingredients and 2 preparation steps are determined as desired
or undesired respectively. For each of the queries we performed a leave-one-out test,
i.e., the corresponding workflow was removed from the repository. Then, we executed
the recipe generation process with the standard approach as well as the complexity-
aware approach. For the complexity-aware recipe construction we chose the parameter
α = 0.5 to consider the query fulfillment and the complexity in equal shares. For
both approaches, we measured the query fulfillment, the complexity, and the combined
complexity-aware criterion of the retrieved as well as of the adapted workflow.
Table 2. evaluation results
query fulfillment complexity combined computation time
standard retrieval 0.83 0.43 0.70 1.15 s
standard adaption 0.92 0.48 0.72 18.73 s
complexity-aware retrieval 0.75 0.28 0.74 1.42 s
complexity-aware adaption 0.87 0.29 0.79 9.49 s
The evaluation results illustrated in Table 2 clearly show that already during com-
plexity-aware retrieval, a less complex workflow is selected. Furthermore, the compu-
tation time of the subsequent adaptation stage is significantly decreased3 . The most im-
portant observation, however, is that with the new complexity-aware approach, the final
complexity is significantly reduced (-40%), while the query fulfillment is only slightly
decreased (-5%). Altogether it can be concluded that the complexity-aware approach
presented in this paper enables the individual construction of easy-to-prepare cooking
recipes with a low preparation complexity.
5 Conclusions and Future Work
This paper presents a new approach to generate easy-to-prepare cooking recipes based
on cooking workflows. The new approach considers a query specified by the user to
automatically generate a cooking workflow matching the users demands and further
considers the complexity of the cooking workflow as an additional criterion. The com-
plexity measure is composed of several criteria including the number of ingredients, the
preparation time and the complexity of preparation steps.
In future work we aim at providing an interface for choosing the desired recipe
complexity. Furthermore, the complexity assessment will be improved and evaluated
by comparing various complexity measures. Finally, we will investigate several other
factors that could be considered during the construction of recipes such as nutritions
and dietary restrictions.
3
The adaptation time depends on the size of the workflow, which is usually smaller, if the
workflow is less complex.
236
Acknowledgements. This work was funded by the German Research Foundation (DFG),
project number BE 1373/3-3.
References
1. Badra, F., Bendaoud, R., Bentebibel, R., Champin, P., Cojan, J., Cordier, A., Desprès, S.,
Jean-Daubias, S., Lieber, J., Meilender, T., Mille, A., Nauer, E., Napoli, A., Toussaint, Y.:
TAAABLE: text mining, ontology engineering, and hierarchical classification for textual
case-based cooking. In: Schaaf, M. (ed.) ECCBR 2008, Trier, Germany, Workshop Proceed-
ings. pp. 219–228 (2008)
2. Bergmann, R., Gil, Y.: Similarity assessment and efficient retrieval of semantic workflows.
Inf. Syst. 40, 115–127 (Mar 2014)
3. Bridge, D., Larkin, H.: Creating new sandwiches from old. In: Nauer, E., Minor, M., Cordier,
A. (eds.) Procs. of the Seventh Computer Cooking Contest (Workshop Programme of the
Twenty-second International Conference on Case-Based Reasoning). pp. 117–124 (2014)
4. Cardoso, J.S., Mendling, J., Neumann, G., Reijers, H.A.: A discourse on complexity of pro-
cess models. In: Eder, J., Dustdar, S. (eds.) Business Process Management Workshops, BPM
2006 International Workshops, BPD, BPI, ENEI, GPWW, DPM, semantics4ws, Vienna,
Austria, September 4-7, 2006, Proceedings. Lecture Notes in Computer Science, vol. 4103,
pp. 117–128. Springer (2006), http://dx.doi.org/10.1007/11837862_13
5. Gaillard, E., Lieber, J., Nauer, E.: Improving ingredient substitution using formal concept
analysis and adaptation of ingredient quantities with mixed linear optimization. In: Kendall-
Morwick, J. (ed.) Workshop Proceedings from (ICCBR 2015), Frankfurt, Germany. CEUR
Workshop Proceedings, vol. 1520, pp. 209–220. CEUR-WS.org (2015)
6. Grace, K., Maher, M.L., Wilson, D.C., Najjar, N.A.: Combining CBR and deep learning
to generate surprising recipe designs. In: Goel, A.K., Dı́az-Agudo, M.B., Roth-Berghofer,
T. (eds.) ICCBR 2016, Atlanta, GA, USA, Proceedings. Lecture Notes in Computer
Science, vol. 9969, pp. 154–169. Springer (2016), http://dx.doi.org/10.1007/
978-3-319-47096-2_11
7. Keppler, M., Kohlhase, M., Lauritzen, N., Schmidt, M., Schumacher, P., Spät, A.: Goethe-
Shaker - Developing a rating score for automated evaluation of cocktail recipes. In: ICCBR
Workshop Proceedings. pp. 101–108 (2014)
8. Minor, M., Montani, S., Recio-Garca, J.A.: Process-oriented case-based reasoning. Informa-
tion Systems 40(0), 103 – 105 (2014)
9. Müller, G., Bergmann, R.: Workflow Streams: A Means for Compositional Adaptation in
Process-Oriented Case-Based Reasoning. In: Proceedings of ICCBR 2014. Cork, Ireland
(2014)
10. Müller, G., Bergmann, R.: CookingCAKE: A framework for the adaptation of cooking
recipes represented as workflows. In: Kendall-Morwick, J. (ed.) Workshop Proceedings from
(ICCBR 2015), Frankfurt, Germany. CEUR Workshop Proceedings, vol. 1520, pp. 221–232.
CEUR-WS.org (2015)
11. Müller, G., Bergmann, R.: Generalization of Workflows in Process-Oriented Case-Based
Reasoning. In: 28th International FLAIRS Conference. AAAI, Hollywood (Florida), USA
(2015)
12. Müller, G., Bergmann, R.: POQL: A New Query Language for Process-Oriented Case-Based
Reasoning (2015), to be submitted to LWA 2015 Trier, Germany
13. Schumacher, P., Minor, M., Walter, K., Bergmann, R.: Extraction of procedural knowledge
from the web. In: Workshop Proceedings: WWW’12. Lyon, France (2012)