Hello Ninjas! Planning is the backbone of success in both our daily lives and the realm of Artificial Intelligence. Just as we meticulously strategize for an examination, AI systems rely on plans to convert objectives into action to achieve a specific goal. In this article, we will learn about a type of planning in AI, i.e., non-linear planning.

Let’s start from the basics.

What is Planning?

Suppose you want to attempt an examination, so what do you do? You prepare your plan according to the difficulty of each chapter of a subject and the resources available. Planning is required everywhere in our day-to-day lives, and the moment we use a plan and do an action, we get a good result.

In Artificial Intelligence, too, a plan is essential to convert objectives into action to achieve a predetermined goal. Planning is a method or process of computing the steps of a problem-solving procedure before executing any of them. Every plan has a domain model in which we initially have the initial state, goal state and set of operators used to convert to the goal state. It makes AI systems more flexible and increases their decision-making capabilities.

There are various types of planning:

Linear Planning

It is also known as Goal stack planning, in which the problem solver uses a single stack containing operators and the goal state. A plan generated by this method has a complete sequence of operators used for achieving the first goal and upcoming goals.

Non-Linear Planning

A plan generated by this method has a partial sequencing of the operators, and it is not composed of a linear sequence of complete sub-plans. Here, the problem is divided into sub-problems so that these sub-problems are dependent on each other.

Hierarchical Planning

A hard problem requires to reach towards the goal state from the initial state. So some of the details of the problem should be eliminated until a solution is found( details are not eliminated from the actual description of operators). And then, the appropriate details can be filled in. Such an approach is called Hierarchical Planning.

Today, we are going to learn about 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:

Suggesting operators, i.e., the list of operators needed for us to get the goal state.

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.

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:

First, we need to create new steps so that they can help us to resolve the pre-condition.

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.

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.

Simple establishment means to assign a value to the variable.

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

We initialize set S to be the set of pre-conditions in the goal state(given to us).

The pre-conditions which are yet to be satisfied are removed from S.

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.

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.

If S becomes empty, we complete the plan by converting the partial order of steps into a total order and instantiate variables if required.

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:

In non-linear planning, we can easily handle complex problems dependent on each other.

As it uses the heuristic approach, it is much easier to find the optimal solution.

It can generate creative and novel solutions to the problems.

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:

The complexity of non-linear planning increases as it includes dealing with interdependent sub-problems.

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: