Using Neural Nets for Max-TCSPs

M. Mouhoub (Canada)


Temporal Reasoning, Neural Networks, Hopfield Model, Constraint Satisfaction, Planning and Scheduling.


In this paper we present an approximation method based on discrete Hopfield neural network (DHNN) for solving Maximum Temporal Constraint Satisfaction Prob lems (Max-TCSPs). A Max-TCSP is a Constraint Satisfac tion Problem (CSP) involving numeric and symbolic tem poral constraints and where a solution satisfying the max imum number of constraints needs to be found within a given deadline. The method that we propose in this paper has the ability to provide a solution with a quality propor tional to the allocated process time. The quality of the solu tion corresponds here to the number of satisfied constraints. This property is very important for real world applications including reactive scheduling and planning and also for over constrained problems where a complete solution can not be found. Experimental study, in terms of time cost and quality of the solution provided, of the DHNN based method we propose, provides promising results comparing to the other exact methods based on branch and bound and approximation methods based on stochastic local search.

Important Links:

Go Back