This project aims to design and implement Javascript visualizations for the book Artificial Intelligence: A Modern Approach. These visualization would work as an educational aid along with the book.
Since each chapters can have a lot of potential visualization and animation, we wanted to approach each of them on a priority basis. The priority of a visualization was judged on the basis of how much time/resources it would take against how much can it enhance the user’s experience as compared to the book.
The initial proposal for the project was to complete the following chapters:
- Chapter 4, Beyond Classical Search
- Chapter 6, Constraint Satisfaction Problems
- Chapter 18, Learning from examples
The final deliverables are:
- Chapter 4, Beyond Classical Search
- Optimization Problem through state space diagram
- Hill Climbing Search
- Simulated Annealing
- Interactive erratic vacuum world
- Searching with No Observation in the erratic vacuum world
- Chapter 6, Constraint Satisfaction Problems
- Intro to CSP with map coloring problem of Australia
- Using CSP to solve simple sudoku puzzles
- Backtracking Search Algorithm in CSPs
- Chapter 3, Solving Problems by Searching
- Bidirectional Search
- Improve color consistency among different diagrams
- Adding sliders to animation diagrams
We decided to deviate from the proposed schedule as well as deliverables due to the following reasons:
- This is an experimental project. We don’t know in advance which method or practice would produce the best kind of visualizations. Due to this, we often had to make visualizations and then throw them away. Hence, the initial proposal is different than the final deliverables.
- Chapter 18, Learning from examples turned out to be more abstract than expected. We did not manage to find many new visualization ideas that were not implemented by others.
- Some diagrams and visualizations that attracted other contributors to the project was intentionally left undone (for example, many contributors showed interest in A* search of Chapter 3). It will help get new people to work on it.
The Optimization problem is introduced through a state space diagram. The goal is to find the state with the highest value for an objective function among all the states. To allow the user to explore the problem, the hill is initially hidden and 25 moves is given to the user to find the highest point. In a move, a user can click on any state to reveal its objective function value. This diagram gives necessary intuition about the problem itself before we move on to solve the problem.
PR : aimacode/aima-javascript#79
Live : http://aimacode.github.io/aima-javascript/4-Beyond-Classical-Search/#optimization-problem
Hill Climbing Search algorithm is introduced to the user in the same kind of environment as the previous diagram. The user can click on any state to start the hill climbing Search from there. The states in the diagram are marked with a different color to denote if the robot can reach the global maxima using hill climbing search from that state. From other states, the robot gets stuck on local maxima which the user easily verify.
PR : aimacode/aima-javascript#80
Live : http://aimacode.github.io/aima-javascript/4-Beyond-Classical-Search/#hill-climbing
Simulated Annealing is visualized using the same kind of state space diagram. The temperature of the running algorithm can be controlled by the user. The robot keeps annealing at the given temperature. The user is asked to slowly decrease temperature to simulate the algorithm.
PR : aimacode/aima-javascript#82
Live : http://aimacode.github.io/aima-javascript/4-Beyond-Classical-Search/#simulated-annealing
The erratic vacuum world problem is introduced with 5 tiles and random initial state. The user can record a sequence of action to perform. The sequence can be run multiple times to verify that it sometimes results in different end states ( due to erratic nature ). The diagram only introduces the problem and not how to solve it.
PR : aimacode/aima-javascript#86
Live : http://aimacode.github.io/aima-javascript/4-Beyond-Classical-Search/#erratic-vacuum-world
The vacuum world with no observation is introduced. 8 random vacuum world is generated and shown to the user. The user is asked to record a set of sequence that can clean all the tiles in all the worlds. Since the 8 worlds are completely random, the user is forced to think of a sequence that can work in any initial state and hence solve the no observation problem.
PR : aimacode/aima-javascript#87
The diagram consist of a map of Australia divided by states. The user is asked to color the states by selecting the color from a small 3-colors palette given and then clicking on the state. It helps develop intuition about the problem through interactivity in the diagram.
PR : aimacode/aima-javascript#89
Live : http://aimacode.github.io/aima-javascript/6-Constraint-Satisfaction-Problems/#csp-with-map-coloring
The diagram shows how the sudoku problem can be formulated and solved by considering it a CSP with 81 variables. An unsolved sudoku problem is shown to the user. Each cell either assigned numbers or dots representing the numbers that can be assigned to it (Domain of that cell). On hovering over any cell, we highlight its row, column and block. We also show the domain of that cell on the right and use color coded ‘crosses’ to show why the domain is reduced. If a domain of a cell has reduced to a single value, hovering over it indicates that it can be assigned to that cell by clicking on it. On hovering, we also highlight the dots in other cells which will be removed (demonstrating the reduction of the domains) if the number is assigned to the cell.
PR : aimacode/aima-javascript#90
Live : http://aimacode.github.io/aima-javascript/6-Constraint-Satisfaction-Problems/#sudoku-example-of-csp
The diagram introduces the backtracking search algorithm to solve CSP without actually describing about the different heuristics. In the Australia map coloring problem, we perform backtracking search by choosing the next variable and next assignment for the variable randomly. We show the domains of all the variables in a table below. When the domain of a variable gets empty and backtracking is required, that column of the table is highlighted. The user can use the slider to explore the states in the backtracking search process.
PR : aimacode/aima-javascript#93
Live : http://aimacode.github.io/aima-javascript/6-Constraint-Satisfaction-Problems/#backtracking-search
Bidirectional Search is visualized in a graph with around 1500 nodes. Side by side comparison of bidirectional bfs and standard bfs is shown in the same graph. The number of nodes expanded in each is shown below the diagram to allow easy comparison. The diagram clearly shows the reason of better performance of bidirectional bfs (as compared to standard bfs) by corresponding it to the areas covered by the circles formed by the frontier of the graph.
PR : aimacode/aima-javascript#94
Live : http://aimacode.github.io/aima-javascript/3-Solving-Problems-By-Searching/#bi-directional-bfs
Chapter 3 contains a lot of visualizations and there was problems with color consistency among them. This PR fixes that problem. PR: aimacode/aima-javascript#95
Chapter 3 contains lots of visualizations that are essentially just animations showing the working of an algorithm in a graph. Sliders for them solves 2 problems. Firstly, the animation stays at its initial state until the user scrolls down to it and interacts with it. Secondly, it is much easier for the user to navigate the different states in the animation.
PR : aimacode/aima-javascript#96
Live : http://aimacode.github.io/aima-javascript/3-Solving-Problems-By-Searching/
PR : aimacode/aima-javascript#97
The entire aima-javascript project is live in github pages
Links to concerned chapters:
Possible improvements to existing diagrams
- For the bfs, dfs and ucs diagrams, there is a section in the right that shows a queue which contains the frontier nodes. As the algorithm progresses, the nodes in these queues are added and removed. Currently, the queue simply updates instantly. It would be nice to have animations allowing the user to see that some new nodes are added or if a node is removed.
- In the node expansion diagram, a zoom effect is used when hovered over a node that can be clicked. It serves 2 purposes: It tells the reader if a node is clickable and also it highlights the same node in the section on the right. A similar kind of effect will be useful in the bfs, dfs and ucs diagrams. The user should match the position of a node in the queue by hovering over the node in the graph itself.
- The depth limited search and iterative depth limited search diagram shows what the algorithm does but not why(which is explained in the book). Such diagrams are not very useful to the user and can be improved upon.
New Visualizations
(Most of these are just ideas and it may not be always possible/feasible to create them)
- Greedy best first search
- A* search
- Recursive best first search
- Heuristic Functions
Possible improvements to existing diagrams
- Genetic Algorithm diagram is very confusing and it's hard to grasp what it is trying to explain. Also, it just shows the algorithm works rather than explaining how it works.
- Online DFS Agent suffers with the same problems. There is no text to accompany it and hence, no explanation. It also simply runs the algorithm without explaining how it works.
New Visualizations
(Most of these are just ideas and it may not be always possible/feasible to create them)
- Small visualizations to demonstrate ridges, plateaus, local maxima and explain how that causes problems. The Hill Climbing Search diagram does that to some extent but that’s not its primary objective.
- Demonstrate variations of hill climbing search like stochastic hill climbing, first-choice hill climbing, random-restart hill climbing etc.
- Local Beam Search
- And-Or Search Trees
- LRTA* Agent
Possible improvements to existing diagrams
- Arc consistency diagram is a simple animation on the algorithm and there is no interaction or proper explanation. It is hard to understand what is happening.
- Backtracking Search diagram currently works without any heuristics. It would be nice to have additional diagrams demonstrating the working of the heuristics that usually accompany the backtracking search algorithm.
New Visualizations
(Most of these are just ideas and it may not be always possible/feasible to create them)
- A diagram to demonstrate k-consistency
- Min-Conflicts algorithm for solving CSP by local search
- Topological Sort
- Tree-CSP-Solver
- There are several unimplemented chapters remaining in the project.
- Generating documentation of the global helper functions.
- Transpilation of ES6 javascript code since it is not yet supported by all the browsers.
Some notes from the experience I gained during the summer:
- It helps to draw the visualization on paper before actually creating it. It allows us to see clearly how it will work and estimate how successful it will be in explaining the concept.
- Always feel free to experiment with new types of visualizations (tutorial types, simple animation, interactive). We clearly don’t have a fixed recipe for what works when. It pays off sometimes to make visualizations and then throw them away simply because it didn’t work as expected or something else works better.
- In the chapters I created, I followed the pattern of first allowing the user to play with the problem himself/herself before actually showing them how it is solved. This method seems to have worked well.(Ex: Node expansion, Map solving problem etc)
- Trying to reuse code from other diagrams sometimes get in the way of creating good visualizations. As pointed out by Amit Patel during several occasions, this project is not one big project with different modules. This is actually like several small projects. It is good to reuse code from different diagrams but make sure it doesn’t get in the way. Some modules of the diagram that are common to many (like sliders) can be made into a separate class in the file ‘globalHelpers.js’.
- Generator functions are quite useful when you have to simulate an animation that shows the working of an algorithm. Generator functions can be controlled from outside the function by the diagram or the user. Also, note that generator functions are slower than normal functions. So, if the diagram needs speed, consider dropping generators. We faced this problem in bi-directional diagram where there were lots of nodes to render.
- Arrow functions are useful when binding events inside a class. Unlike anonymous functions, the ‘this’ keyword is not overwritten inside the arrow functions and hence, the class members are accessible using ‘this’ keyword.
- I personally like d3.js over two.js. D3.js is much more flexible in terms of creating animations and it also have good documentation and support. I don’t have any experience with other libraries.
- Sliders works better than plain animations. Sliders allows the user to control the animation speed according to his/her needs and also, it pauses the animation until the user actually scrolls down to the diagram.
- It is usually a good idea to introduce concepts one by one spanning over multiple diagrams than trying to explain in a single diagram.
Some notes from Peter Norvig
- Its OK to assume that the readers have the books before they go through the diagrams. The text do not need to go deep into the concept which is already explained in the book.
- It is good to have an ‘edit’ mode in the diagrams, so that the users can interact and change the problem environment (We have not implement this in the project yet.)
- The top priority of this project are the readers. So changes that improve reader’s experience are given more priority than something like code refactor.
- Its nice to have consistency among aspects (like color code) of different diagrams in a page.