Recovery from planning failures by creating alternative solutions

For many agents intelligent like robots, being cognitive is an important point in order to complete their missions successfully. Cognitive robots define their mission as a sequence of actions and states. These actions are the sub parts of the whole mission. To conduct their missions successfully, they need to monitor and evaluate every step of the execution. When a mission is given to an intelligent agent, the process called planner, finds a valid sequence of actions to obtain the plan. Then the plan is defined as a sequence of actions that results in the desired state, with the lowest possible cost. The definition of cost may differ from a domain to another. It could be the total time, total power or the plan length. In the GraphPlan planner which is used in this work, the shortest plan is selected. While executing the actions, failures might occur due to different reasons. There might be the cases which the system could fix the problem easily, and sometimes there might be failures that are not easy or impossible to recover by classical methods. Missing actions are also one of the causes of failures. If an agent does not have the proper set of actions to execute a task, a plan is not found, therefore it will result in failure. It is possible for multiple robot teams to overcome such failures. Multiple robot teams can be classified among their capabilities or the way of planning they use. Homogeneous robot teams include multiple robots which all of them have the same capabilities. Heterogeneous robot teams include multiple robots with different capabilities. Because of these differences, a task that is not possible for a robot to execute, could be possible for another. From the planning perspective, there are centralized and de-centralized approaches. In centralized planning, a plan is generated and assigned to the robots by a central control system or a supervisor. In decentralized planning, robots decide on the plan on their own. But in both of the cases, the goal is not individual but general for the whole team. In this work, a decentralized method to overcome the problem of planning failures due to lack of actions for the non-homogeneous systems is proposed. We focus on using the planning graphs to obtain a solution. If a plan results in failure, we propose to get help from another agent. We formulate this 'help' by finding the gap in the graph search. The gap that is causing the planning failure is found by creating the planning graph both in forward and backward directions to obtain the last layers of the search. After obtaining the last graph layers of the both searches, series of algorithms are proposed to find the gap and the final cooperative plan. Therefore, by deleting connective states and their mutex pairs from both sides of the layers results in the gap; and having found this gap, it is possible to plan for the second agent to adopt a complementary plan.