Rearrangement of floor layouts based on constraint satisfaction
Satoshi Ono, Y. Hamada, Shigeru Yamamoto, K. Mizuno, Seiichi Nishihara · 2002
This paper describes a problem for rearranging floor layouts and proposes a system which generates a plan and schedule synchronously. Rearrangement of floor layout (RAFL) is a search problem, which consists of pre- and post-change layouts of objects, workers, and a work hour limit. The goal in solving RAFL is to find a pair of rearrangement plan and its schedule. RAFL deals with planning and scheduling simultaneously, whereas a schedule is usually determined after a plan is found. In RAFL, even if an optimal plan is obtained in advance, a schedule consisting of its elements may not be necessarily feasible. The proposed system uses constraints to represent the required knowledge and tree search algorithm. The system is interactive and informs the users of their search progress. The users may interrupt a search at any time to correct the system if the search is too slow or reaches an insufficient solution. Experimental results show that the system interacted with the user can find a valid solution in scores of minutes, where the time to solve is considerably reduced.