Optimal global planning for cognitive factories with multiple teams of heterogeneous robots

Official URL: http://risc01.sabanciuniv.edu/record=b1586705 (Table of Contents)

We consider a cognitive factory domain with multiple teams of heterogeneous robots where the goal is for all teams to complete their tasks as soon as possible to achieve overall shortest delivery time for a given manufacturing order. Should the need arise, teams help each other by lending robots. This domain is challenging in the following ways: different capabilities of heterogeneous robots need to be considered in the model; discrete symbolic representation and reasoning need to be integrated with continuous external computations to find feasible plans (e.g., to avoid collisions); a coordination of the teams should be found for an optimal feasible global plan (with minimum makespan); in case of an encountered discrepancy/failure during plan execution, if the discrepancy/failure prevents the execution of the rest of the plan, then finding a diagnosis for the discrepancy/failure and recovering from the plan failure is required to achieve the goals. We introduce a formal planning, execution and monitoring framework to address these challenges, by utilizing logic-based formalisms that allow us to embed external computations in continuous spaces, and the relevant state-of-the-art automated reasoners. To find a global plan with minimum makespan, we propose a semi-distributed approach that utilizes a mediator subject to the condition that the teams and the mediator do not know about each other’s workspaces or tasks. According to this approach, 1) the mediator gathers sufficient information from the teams about when they can/need lend/borrow how many and what kind of robots, 2) based on this information, the mediator computes an optimal coordination of the teams and informs each team about this coordination, 3) each team computes its own optimal local plan to achieve its own tasks taking into account the information conveyed by the mediator as well as external computations to avoid collisions, 4) these optimal local plans are merged into an optimal global plan. For the first and the third stages, we utilize methods and tools of hybrid reasoning. For the second stage, we formulate the problem of finding an optimal coordination of teams that can help each other, prove its intractability, and describe how to solve this problem using existing automated reasoners. For the last stage, we prove the optimality of the global plan. For execution and monitoring of an optimal global plan, we introduce a formal framework that provides methods to diagnose failures due to broken robots, and to handle changes in manufacturing orders and in workspaces. We illustrate the applicability of our approaches on various scenarios of cognitive factories with dynamic simulations and physical implementation.