Intelligent Control Group

For a number of years now, ICG has been studying search procedures, a fundamental issue in AI. The approach is mainly practical, i.e. to develop efficient algorithms which reduce the average complexity of classical hard AI search problems which have, in many cases, direct applications to real life problems such as vision, planning, biocomputation etc. Interest has also extended to games (e.g. N-Queens, Sudoku), constraint satisfaction problems (CSP) and combinatorial NP-hard problems such as the maximum clique problem or the Boolean satisfiablility problem (alias SAT) both extensively studied in complexity theory. At present the landmarks of this line of research are:

• BB-MC : one of the best algorithms for the maximum clique problems which uses bit strings effectively to reduce complexity. BBMC has been used successfully in the geometric correspondence problem and applied to find the pose of a robot given a map of the environment and a local observation.
• The best global search heuristic for the N-Queens problem, up to our knowledge.
• A very efficient Sudoku solver which can solve random 25x25 giant locally minimal Sudokus instances in a few seconds.
• A SAT algorithm which uses bit strings to efficiently compute the ‘pure literal’ rule in a DPLL search.