Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Issue title: Constraint Programming for Planning and Scheduling
Article type: Research Article
Authors: Gent, Ian P. | Jefferson, Chris | Kelsey, Tom | Lynce, Inês | Miguel, Ian | Nightingale, Peter | Smith, Barbara M. | Tarim, S. Armagan
Affiliations: School of Computer Science, University of St Andrews, KY16 9SX, UK. E-mail: {ipg,tom,ianm,pn}@dcs.st-and.ac.uk | Computing Laboratory, University of Oxford, UK. E-mail: [email protected] | IST/INESC-ID, Technical University of Lisbon, Portugal. E-mail: [email protected] | Cork Constraint Computation Centre, University College Cork, Ireland. E-mail: {b.smith,at}@4c.ucc.ie
Abstract: We present an evaluation of different AI search paradigms applied to a natural planning problem. The problem we investigate is a particular card game for one player called Black Hole. For paradigms such as SAT and Constraint Programming, the game has the particular advantage that all solutions are the same length. We show that a general version of Black Hole is NP-complete. Then we report on the application of a number of AI paradigms to the problem, namely Planning, Constraint Programming, SAT, Mixed-Integer Programming and a specialised solver. An important feature of Black Hole is the presence of symmetries which arise during the search process. We show that tackling these can improve search dramatically, as can caching states that occur during search. Our implementations as SAT, Constraint Programming and Planning problems are efficient and competitive, allowing detailed empirical evaluation of the strengths and weaknesses of each methodology. Our empirical evaluation shows that Black Hole is winnable approximately 87% of the time, and that given instances can be trivially solved, easy to solve, hard to solve and even intractable, depending on the AI methodology used to obtain solutions.
Keywords: Constraint Programming, planning, empirical evaluation
Journal: AI Communications, vol. 20, no. 3, pp. 211-226, 2007
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
[email protected]
For editorial issues, like the status of your submitted paper or proposals, write to [email protected]
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
[email protected]
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office [email protected]
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
[email protected]
For editorial issues, like the status of your submitted paper or proposals, write to [email protected]
如果您在出版方面需要帮助或有任何建, 件至: [email protected]