Learning to search: From weak methods to domain-specific heuristics

Learning from experience involves three distinct components—generating behavior, assigning credit, and modifying behavior. We discuss these components in the context of learning search heuristics, along with the types of learning that can occur. We then focus on SAGE, a system that improves its search strategies with practice. The program is implemented as a production system, and learns by creating and strengthening rules for proposing moves. SAGE incorporates five different heuristics for assigning credit and blame, and employs a discrimination process to direct its search through the space of rules. The system has shown its generality by learning heuristics for directing search in six different task domains. In addition to improving its search behavior on practice problems, SAGE is able to transfer its expertise to scaled-up versions of a task, and in one case, transfers its acquired search strategy to problems with different initial and goal states.     

An evolutionary approach to support decision making with linear decision models

In this paper we consider decision problems that can be described as linear decision models. These models have been traditionally solved using linear programming, fuzzy linear programming, multiple-objective linear programming or ‘what-if’ analysis. Using these approaches, one encounters a number of difficulties. We propose an ‘evolutionary approach’ to overcome these difficulties. In the proposed approach the decision maker does not have to precisely specify the model (i.e. the objective functions, the RHS values, etc.) at the beginning of the solution procedure. In fact, the model evolves as the solution procedure proceeds.     

Study of unique merging behavior under mixed traffic conditions

Roads in developing countries carry mixed traffic with wide variations in static and dynamic characteristics of vehicles. The traffic flow is also generally devoid of lane discipline, with vehicles occupying any available road space ahead. In such a regime of traffic flow, the phenomena of merging of vehicles at intersections of two roads is complex, warranting further study. The merging maneuvers at T-intersections under congested traffic conditions were studied microscopically through video-recording. In congested situations, the merging vehicle attempts a complex merging maneuver to enter the main traffic stream. Two unique merging processes are commonly observed in mixed traffic: group and vehicle cover merging (these are generally not observed in countries such as US). The author is using these words first time in this study. These reflect the different types of driver behavior – merging in groups, and by taking cover of another vehicle. Probabilistic models for group and vehicle cover merging are developed that capture this unique merging behavior. Comprehensive microscopic data collection and extraction were carried out to study the merging process at T-intersection under congested conditions. Merging models were then estimated using maximum likelihood method with disaggregate data that was collected for a case study T-intersection in Chennai city, India. Such models can find applications in simulation of highly congested traffic flow in a realistic manner under mixed traffic conditions. They can also give insights on devising better traffic control measures at such intersections.     

Planning and acting

A new theory of problem solving is presented, which embeds problem solving in the theory of action; in this theory, a problem is just a difficult action. Making this work requires a sophisticated language for-talking about plans and their execution. This language allows a broad range of types of action, and can also be used to express rules for choosing and scheduling plans. To ensure flexibility, the problem solver consists of an interpreter driven by a theorem prover which actually manipulates formulas of the language. Many examples of the use of the system six given. including an extended treatment of the world of blocks. Limitations and extensions of the system are discussed at length. It is concluded that a rule-based problem solver is necessary and feasible, but that much more work remains to be done on the underlying theory of planning and acting.     

An attempt to understand students' understanding of basic algebra

This paper reports the results obtained with a group of 24 14-year-old students when presented with a set of algebra tasks by the Leeds Modelling System, LMS. These same students were given a comparable paper-and-pencil test and detailed interviews some four months later. The latter studies uncovered several kinds of student misunderstandings that LMS had not detected. Some students had profound misunderstandings of algebraic notation: Others used strategies such as substituting numbers for variables until the equation balanced. Additionally, it appears that the student errors fall into several distinct classes: namely, manipulative, parsing, clerical, and “random.” LMS and its rule database have been enhanced as the result of this experiment, and LMS is now able to diagnose the majority of the errors encountered in this experiment. Finally, the paper gives a process-oriented explanation for student errors, and re-examines related work in cognitive modelling in the light of the types of student errors reported in this experiment. Misgeneralization is a mechanism suggested to explain some of the mal-rules noted in this study.     

Rules and topics in conversation

Rules of conversation are given that specify what can follow what. A system for deciding what makes a reasonable subject for a conversation is shown. Topics are discussed and rules for topic shift are presented.     

Moving words: dynamic representations in language comprehension

Eighty-two participants listened to sentences and then judged whether two sequentially presented visual objects were the same. On critical trials, participants heard a sentence describe the motion of a ball toward or away from the observer (e.g., “The pitcher hurled the softball to you”). Seven hundred and fifty milliseconds after the offset of the sentence, a picture of an object was presented for 500 ms, followed by another picture. On critical trials, the two pictures depicted the kind of ball mentioned in the sentence. The second picture was displayed 175 ms after the first. Crucially, it was either slightly larger or smaller than the first picture, thus suggesting movement of the ball toward or away from the observer. Participants responded more quickly when the implied movement of the balls matched the movement described in the sentence. This result provides support for the view that language comprehension involves dynamic perceptual simulations.     

A learning algorithm for boltzmann machines

The computational power of massively parallel networks of simple processing elements resides in the communication bandwidth provided by the hardware connections between elements. These connections can allow a significant fraction of the knowledge of the system to be applied to an instance of a problem in a very short time. One kind of computation for which massively parallel networks appear to be well suited is large constraint satisfaction searches, but to use the connections efficiently two conditions must be met: First, a search technique that is suitable for parallel networks must be found. Second, there must be some way of choosing internal representations which allow the preexisting hardware connections to be used efficiently for encoding the constraints in the domain being searched. We describe a general parallel search method, based on statistical mechanics, and we show how it leads to a general learning rule for modifying the connection strengths so as to incorporate knowledge about a task domain in an efficient way. We describe some simple examples in which the learning algorithm creates internal representations that are demonstrably the most efficient way of using the preexisting connectivity structure.