Mind change complexity of learning logic programs

The present paper motivates the study of mind change complexity for learning minimal models of length-bounded logic programs. It establishes ordinal mind change complexity bounds for learnability of these classes both from positive facts and from positive and negative facts. Building on Angluin’s notion of finite thickness and Wright’s work on finite elasticity, Shinohara defined the property of bounded finite thickness to give a sufficient condition for learnability of indexed families of computable languages from positive data. This paper shows that an effective version of Shinohara’s notion of bounded finite thickness gives sufficient conditions for learnability with ordinal mind change bound, both in the context of learnability from positive data and for learnability from complete (both positive and negative) data. Let Omega be a notation for the first limit ordinal. Then, it is shown that if a language defining framework yields a uniformly decidable family of languages and has effective bounded finite thickness, then for each natural number m >0, the class of languages defined by formal systems of length <= m: • is identifiable in the limit from positive data with a mind change bound of Omega (power)m; • is identifiable in the limit from both positive and negative data with an ordinal mind change bound of Omega × m. The above sufficient conditions are employed to give an ordinal mind change bound for learnability of minimal models of various classes of length-bounded Prolog programs, including Shapiro’s linear programs, Arimura and Shinohara’s depth-bounded linearly covering programs, and Krishna Rao’s depth-bounded linearly moded programs. It is also noted that the bound for learning from positive data is tight for the example classes considered.

Tactical driver lane change model using forward search

This paper describes the development and evaluation of a tactical lane change model using the forward search algorithm, for use in a traffic simulator. The tactical lane change model constructs a set of possible choices of near-term maneuver sequences available to the driver and selects the lane change action at the present time to realize the best maneuver plan. Including near term maneuver planning in the driver behavior model can allow a better representation of the complex interactions in situations such as a weaving section and high-occupancy vehicle (HOV) lane systems where drivers must weave across several lanes in order to access the HOV lanes. To support the investigation, a longitudinal control model and a basic lane change model were also analyzed. The basic lane change model is similar to those used by today's commonly-used traffic simulators. Parameters in all models were best-fit estimated for selected vehicles from a real-world freeway vehicle trajectory data set. The best-fit estimation procedure minimizes the discrepancy between the model vehicle and real vehicle's trajectories. With the best fit parameters, the proposed tactical lane change model gave a better overall performance for a greater number of cases than the basic lane change model.