What is AI planning?
Given a set of tasks in an environment, AI planning is the branch of Artificial Intelligence focused on arranging these tasks in a feasible way or optimizing a target value.
Where is it used?
AI planning can be applied to many different fields such as:
- Scheduling visits in hospitals to fulfill with a target level of service.
- Arranging delivery routes to save travel time.
- Planning flights maximizing passengers and reducing cost.
- Factory scheduling to minimize the overall production time in a factory.
How does it work?
Two steps are usually required to use AI planning to produce a meaningful result:
Generate a problem description:
This step consists in gathering and formatting the required data for the problem, typically including task-related information such as task duration, resource requirements of the tasks, location of the task, skills required, etc. Also, environment-related such as traveling time from task to task may be necessary, information about the weather, traffic-related data, holidays, etc.
Find a solution to the problem:
Solver: it is a software that given a problem description finds a solution that satisfies all the restrictions provided.
- Optimizer: it is a software that uses a cost function to find a solution that satisfies all restrictions and minimizes the value of that function at the same time. A cost function could be, for example, the traveling time required to serve routes, the finishing time of a set of tasks or anything that is measurable.
Let’s setup a basic Traveling salesman problem in which a salesman has to visit n different places and go back to the starting point using the shortest possible route. In this case we must visit four points with the following traveling times among them:
The simplest method is to test the all possible combinations, in this case only (4 - 1)! = 3 · 2 · 1 = 6 combinations. Let's start:
- p1 -> p2 -> p3 -> p4 -> p1 = 5 + 3 + 1 + 2 = 11
- p1 -> p3 -> p4 -> p2 -> p1 = 1 + 1 + 1 + 5 = 8
- p1 -> p4 -> p2 -> p3 -> p1 = 2 + 1 + 3 + 1 = 7
- p1 -> p2 -> p4 -> p3 -> p1 = 5 + 1 + 1 + 1 = 8
- p1 -> p3 -> p2 -> p4 -> p1 = 1 + 3 + 1 + 2 = 7
- p1 -> p4 -> p3 -> p2 -> p1 = 2 + 1 + 3 + 5 = 11
Thus, we have found the 2 best possible solutions. Both require 7 hours despite the worst combination that is 11 hours (that's a 27% improvement!). In this case we have used brute force, that means just checking all possible combinations, but real world situations are much more difficult as the number of stops is much higher. Imagine checking the combinations for 10 stops, it is (10-1)! that is 3,628,800 different combinations or 20 stops has more than 2 quintillions (2·10¹⁸) combinations.
Finally, just say that there are very efficient ways to explore combinations and discard the ones that do may not lead to a good solution saving a lot of time and computational power.