Modified Backward Chaining Algorithm Using Artificial Intelligence Planning IoT Applications

Modified Backward Chaining Algorithm Using Artificial Intelligence Planning IoT Applications

Pradheep Kumar K. (BITS Pilani, India) and Srinivasan N. (Sathyabama Institute of Science and Technology, India)
DOI: 10.4018/978-1-5225-8555-8.ch009
OnDemand PDF Download:
No Current Special Offers


In this chapter, an automated planning algorithm has been proposed for IoT-based applications. A plan is a sequence of activities that leads to a goal or sub-goals. The sequence of sub-goals leads to a particular goal. The plans can be formulated using forward chaining where actions lead to goals or by backward chaining where goals lead to actions. Another method of planning is called partial order planning where all actions and sub-goals are not illustrated in the plan and left incomplete. When many IoT devices are interconnected, based on the tasks and activities involved resource allocation has to be optimized. An optimal plan is one where the total plan length is minimum, and all actions consume similar quantum of resources to achieve a goal. The scheduling cost incurred by way of resource allocation would be minimum. Compared to the existing algorithms L2-Plan (Learn to Plan) and API, the algorithm developed in this work improves optimality of resources by 14% and 36%, respectively.
Chapter Preview


In today’s world, automation of activities using artificial intelligence finds extensive applications in several areas. To ensure adequate quantum of resources for tasks, the wastage of resources should be avoided. When IoT devices are used the resource constraints become critical. This is mainly because when multiple IoT devices are integrated, each device would be having a separate goal. When multiple devices are integrated, sub-goals of each individual IoT device would be combined to get the final goal of the application.

Automated planning is used to schedule tasks and activities. A plan is a sequence of actions leading to sub-goals and goals. The actions, sub-goals and goals are decided based on the underlying functional behavior of the application.

A collection of actions leading to sub-goals and goals leads to a plan formulation. A number of such plans may be formulated based on the functionality of the application. The plan length is decided based on the number of actions and resource utilization by these actions.

The plans may be formulated by the following methods:

  • Forward Chaining

  • Backward Chaining

  • Partial Order Plans

Forward Chaining

In Forward Chaining approach, a sequence of actions lead to sub-goals and goals. This approach is used in scenarios where the programmer has complete clarity on the actions involved in realizing sub-goals and goals. The information of the entire set of actions is presented in the plan. Plan length in many situations is minimum. It does not handle exceptional conditions and actions. If these need to be handled the programmer needs to address them.

Backward Chaining

In Backward Chaining approach, a sequence of goals or sub-goals lead to actions. In several applications, the outcome or ultimate goal is known, but knowledge of the actions and sub-goals involved in the process is unknown to the programmer. In such situations, the programmer has to work on all actions, tasks and activities associated. Exceptional tasks and actions are also handled as the programmer to explore all these actions. Plan length is always maximum as a number of hidden actions are explored and brought in the plan. This gives designer maximum information to create the application.

Partial Order Planning

In Partial Order Planning, not all actions and sub-goals are available in the plan. This is similar to Backward Chaining approach. Most of the actions are not illustrated and left as an open decision to the application. This is an advanced stage of planning and requires deep learning strategies for effective handling.

In this work, a modified Backward Chaining approach is used where the resource required by an action or sub-goal is computed by categorizing the nature of the action or sub-goal. Later, a priority factor is assigned to the action or sub-goal. The resource utilization is computed based on a proportion of the priority of the action or sub-goal to the sum of the priorities of the actions or sub-goals.

Based on these criteria a Linear Programming Model has been developed and the resource consumption is computed. Resource left unutilized is stored as slack and reused later. In this approach, optimality is guaranteed for the plan length. Compared to L2-Plan and API, the algorithm proposed in this work improves optimality of resource by 14% and 36% respectively.


Literature Survey

Cyber OS as proposed by Akkermans et al in (2017) explains how resource sharing could be done in IoT devices. Here each IoT device is modelled as a node. Further a feature on resource security has also been included to ensure other IoT nodes do not access resource acquired by a particular IoT node. Here lightweight applications and restricted resource access has also been taken care.

Distributed QoS management as discussed by Samie et al in (2016) illustrates the QoS levels of resource constraints in ensuring adequate quantum of resource allocation.

Hierarchical goal based formalism as explained by Shivasankar et al in (2012) illustrates the hierarchical goal based formulation where multiple IoT devices have a sequence of goals.

AI planning strategies that would appreciate smart environments were discussed by Marquardt and Uhrmacher in (2008)

Complete Chapter List

Search this Book: