Artificial Intelligence Research: The Octopus Algorithm for Generating Goal-Directed Heuristic Feedback
Originally published on July 1, 2018 at Blogger; Revised on January 24, 2019.
During the 2010 FIFA World Cup eight years ago, a common octopus named Paul the Octopus drew worldwide attention because it “accurately predicted” all the results of the most important soccer matches in the world (sadly it died by natural courses shortly after that). Perhaps Paul the Octopus just got extraordinarily lucky. Eight years later, as reported by the MIT Technology Review, artificial intelligence has been used in its stead to predict the World Cup (which I doubt would achieve the 100% success rate as the famous octopus did marvelously).
While my research on artificial intelligence (AI) has nothing to do with predicting which team would win the World Cup, octopuses have become one of my inspirations in the past few days. My work is about developing AI techniques that support learning and teaching through solving vastly open-ended problems such as scientific inquiry and engineering design. One of the greatest challenges in such problem-solving tasks is about how to automatically assess student work so that we can automatically generate instructional feedback. Typically, the purpose of this kind of feedback, called formative feedback, is to gradually direct students to some kind of goals, for example, to achieve the most energy-efficient design of a building that meets all the specs. Formative feedback is critically important to ensuring the success of project-based learning, a common pedagogy for teaching and practicing scientific inquiry and engineering design. Based on my own experience, however, many students have great difficulties making progress towards the goal in the short amount of time typically available in the classroom. Given the time constraints, they need help on an ongoing basis. But it is unrealistic to expect the teacher to simultaneously monitor a few dozen students while they are working on their own projects and provide timely feedback to each and every one of them at the same time. This is where AI can help. This is the reason why we are developing new pedagogical principles and instructional strategies, hoping to harness the power of AI to spur students to think more deeply, explore more widely, and even design more creatively.
Although this general idea of using AI in education makes sense, developing reliable algorithms that can automatically guide students to solve massively open-ended problems such as engineering design is by no means a small job. Through three months of intense work in this field, I have developed genetic algorithms that can be used to find optimal solutions in complex design environments such as the Aladdin CAD software. These algorithms were proven to be effective for optimizing certain engineering problems, but to call them AI, we will need to identify what kind of instructional intelligence of humans that they are able to augment or replace. In my current point of view, an apparent class of AI applications is about mimicking certain teaching capacities of peers and instructors. In order to create an artificial peer or even an artificial instructor, we would have to figure out algorithms that simulate the interactions between a student and a peer or between a student and an instructor, in particular those related to heuristics — one of three keys to the mind according to German psychologist Gerd Gigerenzer.
In teaching, heuristics generally represent scaffolding methods for inspiring and guiding students to discover knowledge step by step on their own. In computer science, genetic algorithms are also called metaheuristic algorithms, variations of heuristic algorithms. Heuristics generally represent computational methods for searching and optimizing solutions step by step based on updated data. The similarity between heuristics in teaching and heuristics in computing is that the answer is not given right away— only a suggestion for understanding or solving a problem based on currently available information is provided. The difference is that, in the case of teaching, we withhold the answer because we want students to think hard to discover it by themselves, whereas in the case of computing, we don’t really know what the optimal answer may be.
Despite the commonality, there are many things to consider when we try to use computational heuristics to build educational heuristics. In teaching, an optimization algorithm that yields the best solution in a long single run is not very useful as it doesn’t provide sufficient opportunities for engaging students. You can imagine that type of algorithm as someone who does something very fast but doesn’t pause to explain to the learner how he or she does the job. To create a developmentally appropriate tool, we will need to slow down the process a bit — sort of like the creeping of an octopus — so that the learner can have a chance to observe, reflect, internalize, and catch up on their own when AI is solving the problem step by step (“give some help, but not too much” — as an experienced instructor would act in heuristic teaching). This kind of algorithm is known as local search, a technique for finding an optimal solution in the vicinity of a starting point that represents the learner’s current state (as opposed to global search that casts a wide net across the entire solution space, representing equally all possibilities regardless of the learner’s current state). Random optimization is one of the local search methods proposed in 1965, which stochastically generates a set of candidate solutions distributed around the initial solution in accordance with the normal distribution. The graphical representation of a normal distribution is a bell curve that somewhat resembles the shape of an octopus (Figure 1). When using a genetic algorithm to implement the local search, the two red edge areas in Figure 1 can be imagined as the “tentacles” for the “octopus” to sense “food” (optima), while the green bulk area in the middle can be imagined as the “body” for it to “digest the catches” (i.e., to concentrate on local search). Once an optimum is “felt” (i.e., one or more solution points close to the optimum is included in the randomly generated population of the genetic algorithm), the “octopus” will move towards it (i.e., the best solution from the population will converge to the optimum) as driven by the genetic algorithm. The length of the “tentacles,” characterized by the standard deviation of the normal distribution, dictates the pace in which the algorithm will find an optimum. The smaller the standard deviation, the slower the algorithm will locate an optimum.
I call this particular combination of random optimization and genetic algorithm the Octopus Algorithm as it intuitively mimics how an octopus hunts on the sea floor (and, in part, to honor Paul the Octopus and to celebrate the 2018 World Cup Tournament). With a controlled drift speed, the Octopus Algorithm can be applied to incrementally correct the learner’s work in a way that goes back and forth between the human and the machine, making it possible for us to devise a learning strategy based on human-machine collaboration as illustrated in Figure 2. Another way to look at this human-machine relationship is that it can be used to turn a design process into some kind of gaming (e.g., chess or Go), which challenges students to compete against a computer towards an agreed goal but with an unpredictable outcome (either the computer wins or the human wins). It is our hope that AI would ultimately serve as a tool to train students to design effectively just like what it has already done for training chess or Go players.
How does the Octopus Algorithm work, I hear you are curious? I have tested it with some simple test functions such as certain sinusoidal functions (e.g., |sin(nx)|) and found that it worked for those test cases. But since I have the Aladdin platform, I can readily test my algorithms with real-world problems instead of some toy problems. As the first real-world example, let’s check how it finds the optimal tilt angle of a single row of solar panels for a selected day at a given location (we can do it for the entire year, but it takes much longer to run the simulation with not much more to add in terms of testing the algorithm), as shown in Figure 3. Let’s assume that the initial guess for the tilt angle is zero degree (if you have no idea which way and how much the solar panels should be tilted, you may just lay them flat as a reasonable starting point). Figure 4 shows the results of four consecutive runs. The graphs in the left column show the normal distributions around the initial guess and the best emerged after each round (which was used as the initial guess for the next round). The graphs in the right column show the final distribution of the population at the end of each round. The first and second runs show that the “octopus” gradually drifted left. At the end of the third run, it had converged to the final solution. It just stayed there at the end of the fourth run.
When there are multiple optima in the solution space (a problem known as multimodal optimization), it may be appropriate to expect that AI would guide students to the nearest optimum. This may also be a recommendation by learning theories such as the Zone of Proximal Development introduced by Russian psychologist Lev Vygotsky. If a student is working in a certain area of the design space, guiding him or her to find the best option within that niche seems to be the most logical instructional strategy. With a conventional genetic algorithm that performs global search with uniform initial selection across the solution space, there is simply no guarantee that the suggested solution would take the student’s current solution into consideration, even though his/her current solution can be included as part of the first generation (which, by the way, may be quickly discarded if the solution turns out to be a bad one). The Octopus Algorithm, on the other hand, respects the student’s current state and tries to walk him/her through the process stepwisely. In theory, it is a better technique to support personalized learning, the number one in the 14 grand challenges for engineering in the 21st century posed by the National Academy of Engineering of the United States.
Let’s see how the Octopus Algorithm finds multiple optima. Again, I have tested the algorithm with simple sinusoidal functions and found that it worked in those test cases. But I want to use a real-world example from Aladdin to illustrate my points. This example is concerned with determining the optimal orientation of a house, given that everything else has been fixed (Figure 5). The orientation will affect the energy use of the house because it will receive different amounts of solar radiation through the windows at different orientations.
By manual search, I found that there are basically four different orientations that could result in comparable energy efficiency, as depicted in Figure 6.
Now let’s pick four different initial guesses and see which optimum each “octopus” finds. Figure 7 shows the results. The graphs in the left column show the normal distributions around the four initial guesses. The graphs in the right column show the final solutions to which the Octopus Algorithm converged. In this test case, the algorithm succeeded in ensuring nearest guidance within the zone of proximal development. Why is this important? Imagine if the student is experimenting with a southwest orientation but hasn’t quite figured out the optimal angle. An algorithm that suggests that he or she should abandon the current line of thinking and consider another orientation (say, southeast) could misguide the student and is therefore unacceptable. Once the student arrives at an optimal solution nearby, it may be desirable to prompt him/her to explore alternative solutions by choosing a different area to focus and repeat this process as needed. The ability for the algorithm to detect the three other optimal solutions simultaneously, known as multi-niche optimization, would be helpful but may not be essential in this case.
There is a practical problem, though. When we generate the normal distribution of solution points around the initial guess, we have to specify the standard deviation that represents the reach of the “tentacles” (Figure 8). As illustrated by Figure 9, the larger the standard deviation (“a fatter octopus”), the more likely the algorithm will find more than one optima and may lose the nearest one as a result. In most cases, finding a solution that is close enough may be good enough in terms of guidance. But if this weakness becomes an issue, we can always reduce the standard deviation to search the neighborhood more carefully. The downside is that it will slow down the optimization process, though.
In summary, the Octopus Algorithm that I have invented seems to be able to accurately guide a designer to the nearest optimal solution in an engineering design process. Unlike Paul the Octopus that relied on supernatural forces (or did it?), the Octopus Algorithm is an AI technique that we create, control, and leverage. On a separate note, since some genetic algorithms also employ tournament selection like the World Cup, perhaps Paul the Octopus was thinking like a genetic algorithm (joke)? For the computer scientists who happen to be reading this article, it may also add a new method for multi-niche optimization besides fitness sharing and probabilistic crowding.
