Research Article
Developing Visualization Tool for Teaching AI Searching Algorithms
Faculty of Engineering and Information Technology, Al-Azhar University, Gaza, Palestine
A few algorithm visualization tools have been developed recently, (Naps et al., 2007; Stephen et al., 2007; Cooper, 2007; Jarc et al., 2000). Researchers have introduced many innovations to their visualization tools, including color, smooth transitions from one interesting state to another, sound and three-dimensional animations.
While there have been very few thorough evaluations the general view appears to be that algorithms visualization tool do not help much in so far as student learning is concerned. In some ways this is not surprising as many of these tools were developed more with a view to fancy graphics rather than pedagogy. However, even for tools which have a specific pedagogic focus the evaluations are vague (Karavirta et al., 2006; Hilbert, 2006; Moses et al., 2004; Baker et al., 1996).
We believe that algorithm visualization tools can help student in learning, however, they need to be designed and evaluated appropriately. In order to design our algorithm visualization tools for artificial intelligence searching algorithms we have carefully analysed students' learning difficulties and developed an algorithm visualization tools to address these difficulties.
Our analysis of students` learning difficulties revealed that the students who developed good visual representations of the changing data structures gained a better understanding of the searching algorithms. The algorithm visualization tool that we have developed is designed to help all students in developing such visual representations. This, together with the facility to experiment with different search parameters, like heuristic function and receive immediate visual feedback, enables most students to achieve a better understanding of searching concepts and processes.
In the period between 1/9/2005 and 1/9/2007, 90 students were randomly chosen from Al-Azhar University in Gaza. All students were senior level students enrolling in the Artificial Intelligence course. The students had no prior knowledge in the subject matter to be taught.
Students learning difficulties: Artificial intelligence is studied at senior level in the Faculty of Engineering and Information Technology of Al Azhar University in Gaza. Typically students have already taken courses such as data structures and algorithm analysis. However, many students have considerable difficulty in understanding searching algorithms, even students who previously had little trouble with the basic searching and sorting. In the course of teaching artificial intelligence subjects over the past few years we noticed many occurrences of the difficulties as follows:
• | Some students have difficulty in translating the algorithms into a dynamic behaviour of data structures in executable programs. The text of the algorithms is generally short.. Some students find this difficult to comprehend. Some students are comfortable with one data structure but are not comfortable with another data structure. |
• | Many students learn the text of an algorithm and can generally show the operation of the algorithm on a small problem, but their understanding remains shallow. The deeper understanding which they are lacking includes forming a reasonable general framework of the relationships between the different searching algorithms and predicting the kinds of behaviours that would be expected from any small change in searching parameters. |
In general, students` learning difficulties can be categorized into two types:
• | Problems with the individual steps of an algorithm and |
• | Problems with qualitative judgments about algorithm behaviour and comparison of different searching algorithms. |
Single step mode: This group of difficulties relate to understanding what happens at each step of the algorithm, for example, given a tree, which node will depth first search expand next? What will be its children? Which nodes will move from the open set to the closed set? The single step mode of our algorithm visualization tool is designed to help students with these issues.
Qualitative judgments: Most students who understand the single steps mode of the searching algorithms are unable to answer questions about qualitative behaviour, for example, over a range of problems would depth first search be better than breadth first search? Will the heuristic function hf1 be better than the heuristic function hf2? The all steps mode of our tool is designed to help students with these issues.
The visualization tool: The Artificial Intelligent searching (Kehoe et al., 1999; Gloor, 1992) visualization tool is based on the Water Jug problem. The Water Jug problem is defined as follows:
• | You have two jugs, one of which can holds four litters of water, the other can holds three litters of water and an endless supply of water (Fig. 1). Your task is to get two litters of water in the four litter`s jug, but you have no way of measuring two litters directly! You can't put "roughly" two litters in and hope for the best. |
Single step mode: This mode is designed to assist the student in understanding each step of the various searching algorithms. A screen snapshot of this mode is shown in Fig. 2.
Fig. 1: | Instance of the water jug problem |
Fig. 2: | Single step mode |
The rules of the water jug problem are shown in a separate window. Different colors are used to distinguish the heuristic function and the data structure graph. When the goal state is found the entire solution path is shown. The text of the algorithm is also available in a separate window if the student needs it. At each click on the Next button one step of the algorithm is carried out, the steps show which rule being executed are highlighted and the updated data structures are drawn.
All steps mode: All steps mode is designed to assist students in understanding qualitative aspects of the behaviour of a searching algorithm and to make comparisons between algorithms. It is the main advantage in the tool.
In the all steps mode the detail of each state is shown and the links between states (Fig. 3). All steps mode reveals how the search space is explored and shows the focus node of the search.
Fig. 3: | All steps mode, depth first search |
The number of nodes expanded in a search is based on the rules and type of algorithm. Figure 3-5 show the results of three different search algorithms for the problem given in Fig. 1. It is quite easy to see that A* search (Fig. 5) expands the smallest number of nodes and breadth first search (Fig. 4) expands the largest number of nodes. For other instances of the problem (and this is a key concept the students must learn). A* search will usually be the best; while depth first search and breadth first search will show considerable variation.
Back step mode: This feature helps students to undo steps done recently. Student can undo all steps taken already and start over again with single steps mode or all steps mode.
Evolution of the visualization tool: In the first version of the visualization tool, we had scroll bars to be used when search graph is too big to fit in the predefined window. In the new version of the visualization tool, we had to remove the scroll bars.
Fig. 4: | Single step mode, breadth first search |
We were unhappy with them because students can lose orientation as the system writes in one place while they attempt to scroll elsewhere. We thought of using `zoom-out' strategy in the new version of the visualization tool that is re-render the search graph at a lower level of magnification; however very bushy breadth first searches would still be a problem.
Coverage of the tool: The tool contains all of the searching algorithms that usually taught in an undergraduate course of artificial intelligence: such as depth first search, breadth first search, best first, branch and bound search and A* search. The manhattans distance, city block distance heuristics and predefined heuristic functions are also supported.
Objectives of this study: This study aims at achieving the following objectives:
• | To develop visualization tool to be used in teaching AI searching algorithms. |
• | To measure the effect of this visualization tool on students` performance in AI searching algorithms (measured by exam results). |
Fig. 5: | All steps mode, A* search |
• | To compare the effectiveness of using visualization tools with lecture to the conventional teaching methods without visualization tool. |
• | To measure the effect of gender and visualization tools on teaching AI searching algorithms. |
Questions of this study:
• | Are there significant differences in performance between students taught using the conventional method and students taught using visualization tools? |
• | Are there significant differences in performance between students taught using old visualization tool and the new visualization tool? |
• | Are there significant differences in students` evaluation of the benefits of using visualization tools according to sex in any of the visualization tool groups? |
• | What are the students` evaluations of the benefits of using visualization tools? |
• | Is there a relationship between students` performance in visualization tool groups and their evaluation of the benefits of using visualization tool? |
Hypothesis:
• | There are no significant differences in performance between students taught using the conventional method and students taught using the visualization tools. |
• | There are no significant differences in performance between students (males and females) in visualization tools. |
• | There are no significant differences in performance between students taught using the old visualization tool and the new visualization tool. |
• | Students` evaluation of the benefits of using visualization tools is strongly positive. |
• | There is a strong positive relationship between students` performance in visualization tool groups and their evaluation of the benefits of using visualization tool. |
• | There are no significant differences in students (males and females) evaluation for the benefits of visualization tools to sex. |
Procedure and data collection: Ninety students were selected to participate in this evaluation and randomly assigned to 3 groups (15 male and 15 female for each group):
Group 1 (the control group): This group was taught using the conventional teaching method (lecture and textbook).
Group 2 (old version of the visualization tool group): This group was taught using the lecture and the old version of the visualization tool.
Group 3 (new version of the visualization tool group): This group was taught using the lecture and the most recent version of the visualization tool.
At the end of instruction all students were given an exam in the subject matter studied and their exam grades were recorded. These grades are to be used to examine possible differences in performance between those groups.
Statistical analysis: A one-way ANOVA test was conducted on the grades of the exam for students in groups: (1, 2, 3). To determine if there were any significant differences in students performance between the conventional group and the visualization tool groups. This test was conducted on the entire sample (90 students). If significant differences are to be found, the Scheffe multiple comparison test is to be used to determine differences between group pairs and to investigate possible advantages of one group over another.
An independent-sample-t test was conducted on the exam grades for male and female students in visualization tool groups (2, 3) one group at a time, to determine if significant differences in performance exist between male and female students in each visualization tool group. The same test was performed on the student evaluation scores to determine if significant differences in performance exist between male and female students in evaluation of each visualization tool group.
For each visualization tool group (2, 3), the correlation coefficient for students evaluation of the benefits of using visualization tool and their performance was computed. The average of total score of students for each group (2, 3) is computed to determine the degree of students` evaluation.
Table 1 shows the results of the ANOVA test for the conventional (control) group and visualization tool groups. The table shows that there are significant differences between the groups.
Table 2 shows the results of Scheffe multiple comparisons between group pairs. It can be seen from Table 2 that there are significant differences in performance between the 3 groups in favor of: firstly the new visualization tool group, secondly old visualization tool group and at last the conventional group. That indicates that using the visualization tools is better than the conventional methods without the tools.
Table 3 shows the results of the independent samples-t-test between male and female students in the visualization tool groups. The results show that: there are no significant differences in performance between male and female students in any of the visualization tool groups. This indicates that visualization tools are stable and can be implemented effectively.
Table 4 shows the results of the independent samples-t-test of students` evaluation scores to determine if significant differences in performance exist between male and female students in evaluation of each visualization tool group.
Table 1: | ANOVA table for the exam grades for groups (1, 2, 3) |
Significant at the (0.05) level |
Table 2: | Scheffe multiple comparisons between group pairs |
*The mean difference is significant at the 0.05 level |
Table 3: | The independent samples t-test results for male and female students exam grades in |
Table 4: | The independent samples t-test results for male and female students` Evaluation scores of visualization tool groups |
Table 5: | Correlation between student evaluation of the benefits of using visualization tool and their performance |
*Correlation is significant at the 0.01 level |
The results show that: there are no significant differences in students` evaluation of visualization tool groups between male and female students. This indicates that visualization tools are stable and can be implemented effectively.
Table 5 shows the correlation coefficients between students` performance in visualization tool groups (2, 3) and their evaluation of the benefits of using visualization tools. These results show a strong positive relationship between the performance of students and their evaluation of the benefits of using visualization tools.
We have described a visualization tool that we developed for helping students to learn artificial intelligence searching algorithms. Common difficulties experienced by students in studying searching algorithms were identified and the algorithm visualization tool was designed to help with these difficulties. The tool operates in single step mode, back step mode and all steps mode. Single step mode facilitates the learning of the individual steps of the algorithm. The all steps mode facilitates learning of the qualitative behavior and comparison of algorithms, while the back step mode undo the steps already done by the student. Furthermore, we conducted an evaluation study of the tool.
The results of this study suggest that algorithm visualization tools can enhance the student understanding in AI searching algorithms. The tool can be effective only under the supervision of a human instructor. The study also shows that the performance level of students (males and females) in the new version of the visualization tool is improved more than the performance level of students (males and females) in the old version of the tool.
Also, the study has shown that gender is not factors affecting the use of visualization tools. Finally, the results suggest that the performance of students taught using visualization tools is strongly related to their evaluation of the benefits of using the visualization tools.
Further research is needed in the possible use of other visualization tools, because visualization proved to be an effective tool for aiding students in their study at the university level.