Non-Linear Planning in AI

Non-Linear Planning in AI

In non-linear planning, the problem is divided into sub-problems so that these sub-problems are dependent on each other. It is a partial ordering planning, i.e., as the actions are not arranged in a specific order. In non-linear planning, we don’t commit the actions until and unless necessary, so it is also called the least commitment planning. Here, the operators used to solve one subproblem interfere with the solutions of the previous subproblem.   

Example 1

In this example, the initial state is dependent on State 1, State 2, State 3, and the final state. State 3 is dependent on State 2, State 1, and the final state. State 2 is dependent on the final state. Here all the states are dependent on each other to reach the final state. This is the most basic example of non-linear planning.

Example 2

Here, in this example, 

The initial state is - B is available on A, D is available on C, and A & C are available on the table. B & D are clear.

The final state is - D is available on B, B is available on C, C is available on A, A is available on the table, and D is clear.

According to the concept of non-linear planning, we need to divide it into different subgroups. To reach the final state, we have to unstack A, and B, i.e., putting A on the table.  Then we have to unstack C and D and put C on A. Then put B on C. At last, we put D on B.

Constraints Posting in Non-Linear Planning

Non-Linear planning follows certain types of constraint posting. Constraint posting builds up a plan by considering three important things:

1. Suggesting operators, i.e., the list of operators needed for us to get the goal state.
    
2. Once the list of operators is ready, next, we need to know the sequence of how we can apply those operators, i.e., which operators are to be applied first.
    
3. Then it will produce the binding,i.e., the association between the variables and the operators.
    

So the constraint posting will perform a plan by suggesting certain operators, and it will order them, and then, at last, it would try to identify or describe specific bindings between variables & operators.

Components of a Non-Linear Planning

Non-Linear planning in AI consists of the following:

Set of Steps 

Set of Steps, say, {S1, S2, S3….} are the actions, having an operator description, pre-conditions, and post-conditions (result after applying a particular operator).

Set of Casual Links 

Set of casual links, say, {.....{S1CS2}....} where there is a step S1 and a step S2, and in between them, there exists a pre-condition. This pre-condition states that if you have to perform S2, pre-condition C is to be achieved by performing step S1. Here, steps, S1 and S2, are linked with some pre-condition.

Set of Ordering Constraints

Set of Ordering Constraints, say, {.....{S1CS2}....} represents that S1 should be performed before performing S2.

Heuristics for Non-Linear Planning Using Constraint Posting

During the ordering of operators and getting a complete set of sequence of operators list, we use the following steps:

1. First, we need to create new steps so that they can help us to resolve the pre-condition.
    
2. Then we promote the operators. Sometimes we may have planned to put a particular operator in the last position; this operator may need to be applied in the second step. In such case, we promote that operator up in that Sequence.
    
3. Then comes Declobbering. Suppose you have solved a subproblem S1 and S3. But to solve S3, S1 is to be solved first. So, we place S2 between these two steps such that S3 can be easily applied, which was previously prevented by S1. 
    
4. Simple establishment means to assign a value to the variable.
    
5. Next is Separation, i.e., preventing the assignment of certain values to a variable.

All these steps are not necessarily applied to each problem statement. It depends on our requirements; we will use either all or only some of these.

Algorithm of Non-Linear Planning

1. We initialize set S to be the set of pre-conditions in the goal state(given to us).
    
2. The pre-conditions which are yet to be satisfied are removed from S.
    
3. We achieve that pre-condition by using one of the techniques, i.e., step addition, promotion, declobbering, simple establishment, or separation, depending upon the requirement.
    
4. Then all the steps are reviewed as there can be cases when new steps are introduced by step addition and also to check if any pre-condition is unachieved. Then these unachieved pre-conditions are added to set S.
    
5. If S becomes empty, we complete the plan by converting the partial order of steps into a total order and instantiate variables if required.
    
6. We go to step 2 until all the pre-conditions have been satisfied.

Advantages and Disadvantages of Non-Linear Planning 

The advantages of non-linear planning in AI are:

1. In non-linear planning, we can easily handle complex problems dependent on each other.
    
2. As it uses the heuristic approach, it is much easier to find the optimal solution.
    
3. It can generate creative and novel solutions to the problems.
    
4. It can handle incomplete or uncertain information and estimate the possibility of different outcomes and then make decisions.

The disadvantages of non-linear planning in AI are:

1. The complexity of non-linear planning increases as it includes dealing with interdependent sub-problems.
    
2. The search space of non-linear planning can become huge as the sub-problems increase. 

Frequently Asked Questions

How does non-linear planning in AI differ from linear planning in AI?

Linear planning starts with a goal to be achieved, but non-linear planning begins with a partial plan that is expanded and refined.

Can non-linear planning in AI handle problems with uncertain or incomplete information?

It can easily incorporate uncertainty and probabilistic reasoning into the planning process.

What are some real-world applications where non-linear planning can be beneficial?

It can be used in various domains like robotics, supply chain management, game design, etc.

Can non-linear planning in AI generate optimal solutions for complex problems?

The complex search space involved in non-linear planning makes it challenging to always guarantee finding an optimal solution.

What are the specific algorithms commonly used in non-linear planning in AI?

These algorithms are - Hierarchical Task Networks (HTNs), Partial Order Planning (POPs), and Constraint Satisfaction Problems (CSPs).

Conclusion

In conclusion, non-linear planning in AI offers a valuable approach to problem-solving, enhancing the flexibility and decision-making capabilities of AI systems. In this article, we learned how non-linear planning divides the problem into subparts, allowing for partial ordering of actions and the least commitment planning approach. 

Further, we explored the components of a non-linear plan, the concept of constraint posting, and the heuristics used in the planning process. In summary, non-linear planning provides an efficient way to convert objectives into action, contributing to the success of AI systems in various domains. 

To learn more about Artificial Intelligence, we recommend reading the following articles:

• Advantages and Disadvantages of AI
• Expert System in AI
• Top 10 Artificial Intelligence projects
   

If you liked our article, do upvote our article and help other ninjas grow.  You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, System Design, and many more!

Happy Learning!