Project 1: Knowledge Retrieval - Search Algorithms Implementation

For this part, we have created a Functional Object-Oriented Network (FOON) merging your labeling done in the previous part. Now, you have to implement search algorithms so that it can extract a task tree to prepare any dish existing in FOON. A task tree has the exact same structure of a subgraph.

1. FOON (A .txt file)

2. A goal object to search.

3. List of ingredients and utensils available in the kitchen (A .txt file)

FOON, sample goal objects and a kitchen file will be found in Canvas Files section.

1. Implement two search algorithms.

a. You can implement any uninformed search algorithm (e.g. BFS, DFS etc.) that you think suitable here. If there are many possible
paths to reach the desired node, just output the first one that you find. A path is considered a solution if all the ingredients in that path are available in the kitchen.

B. Modify the first search algorithm by using a heuristic. To explore a node, instead of choosing a path randomly from various options, choose a path that requires minimum number of input objects. For example, if you find that scrambled egg can be prepared with either {egg, oil, cheese, onion} or {egg, oil, salt}, take the path that requires {egg, oil, salt}. Because, in this path, you need fewer input objects.

2. Visualize the retrieved task trees and check if they make sense. You should use it to debug your program.

3. Save two task trees (one for each algorithm) in two separate .txt files. If a task tree cannot be retrieved (the kitchen provided to you doesn’t contain all necessary cooking utensils or ingredients), just print which items are missing.

The pseudocode provided here is for the algorithm mentioned in the original FOON paper. You solution can be different than the following one:

1. Identify the goal node G and determine whether it exists in the network. If it does, proceed to next step.

2. Identify items that you have in kitchen and keep them in a list K.

3. Create a queue S that contains items you do not know how to make Enqueue G to S.

4. Dequeue element E from S. If E is not in K, Search for all functional units in FOON that has E as one of its output nodes. Add candidate units to list C. For your second algorithm, sort C based on the number of input in a functional unit.

5. Remove the first candidate and check if we have input nodes in K. If we have all input nodes, add functional unit to final tree T. Add them to K. If any input nodes are missing, add them to S. Add E back to S.

6. If K contains G, then end the search and return the final list of steps (functional units) T; else, go back to step 4 and keep searching to find out how to make needed items.

Two task trees saved in two separate .txt files, one for each searching algorithm.

I will have my own kitchen file (different from what you will have) and a few objects to search. With this kitchen file, I will search the objects in FOON and check the retrieved task trees.

You can use any programming language for this project. Create a zip file including everything that is required to run your program. That is,

? FOON (.txt file)

? Your code

? Kitchen File

? Two retrieved task trees in two separate .txt files.

? A readme file with the instructions about how to run your program. Also mention if any package needs to be installed.

Name the zip file with your UID (e.g. U13611582.zip). Submit it on Canvas.

This part of the project is worth 50% of your final project’s grade