Solving flow shop problems using a forward-chaining partial-order planner

Abstract: Planning is the task of putting together a sequence of actions that takes a start state to a goal state. Since planning is a crucial part of human intelligence it is also a crucial part of artificial intelligence. As with human planning there are many different ways of AI planning and many different problems to plan. This thesis aims to discover how well a specific way of AI planning performs on a specific sort of problem. The planner that was investigated is called the POPF planner which is a forward-chaining partial-order planner which is an attempt at merging two different ways of planning. This was done to see how well this relatively uncommon method of planning compares to other more traditional methods of planning such as forward-chaining planners when solving a flow shop problem. A flow shop problem is a problem regarding minimizing the idle time for a facility that contains a number of m machines that need to do n jobs. Each of the n jobs 1…n have to be processed on m machines 1…m in that order. Tests were done to see how the POPF planner performed in comparison to planners that work differently. This was done by creating a flow shop problem suitable for testing and then testing the POPF planner on the problem and comparing the results to two other planners. The other planners being the COLIN and TFD planners which both work differently from each other and the POPF planner. Suggestions were also made for how the POPF planner could potentially be improved using additional methods such as landmarks. The results of the test show that the POPF planner is better than the COLIN planner and as good if not better than the TFD planner depending on the complexity of the problem. An additional test was done using the POPStar planner that specializes in the sorts of problem that was created for testing. This POPStar planner outperformed the other planners as expected but it loses in flexibility since it cannot solve problems defined in PDDL. The final results show that the POPF planner performs on a similar level to other general planners when it comes to solving flow shop problems while still having some of the benefits of being a partial-order planner such as being more flexible than a totally-ordered planner.