| Paper Details: | Downloads: 1450 |
| Serial Number: | P1121521384
|
| Title: | A novel Hybrid Search for Minimal Perturbation Problems based on Backjumping and Dynamic backtracking methods
|
| Authors: | EL GRAOUI EL MEHDI and BENELALLAM IMADE and BOUYAKHF EL HOUSSINE
|
| Abstract: | Many real-life problems in Artificial Intelligence (AI) as well as in other areas can be efficiently modeled and solved using constraint programming techniques. In many real-life scenarios the problem is partially dynamic. For example, once a change appears in the environment, after the original problem resolution, this change should be reflected in the new solution. The minimal perturbation problem considers such changes, as well as the initial solution to define a new problem whose solution should be as close as possible to the initial solution.
In this paper, we propose two new approaches: HS MPP backjumping and HS MPP dynamic backtracking. These algorithms are based on HS MPP approach (Hybrid Search for Minimal Perturbation Problem) [1]. They rely on the intelligent backtracking methods, namely the backjumping and dynamic backtracking which allow reducing the number of constraints tested and thus the computational time. The evaluation of performance is applied for random binary problems and meeting scheduling problems, with the criteria of computation time, number of constraints checks and number of visited nodes. Finally, the empirical results with these search methods show the efficiency of our proposed algorithms.
|
| Keywords: | Intelligent backtracking, back-jumping, HS MPP, HS MPP BJ, dynamic backtracking, HS MPP DB, minimal perturbation problem, Constraint Satisfaction Problem (CSP), Meeting Scheduling Problem (MSP).
|
| Journal/Conference: | International Journal of Artificial Intelligence and Machine Learning
|
| Volume: | 15
|
| Issue: | 1
|
| Submission Date: | 5/21/2015 12:00:00 AM
|
| Review Date: | 6/1/2015 12:00:00 AM
|
| Publishing Date: | 6/25/2015 12:00:00 AM
|
| Article Downloads: | 1450
|
| Download: |
|