| Along with the development of Artificial Intelligent(AI), unmanned vehicles become more and more small in body type and smart in intelligence. Multi-collaborated unmanned vehicles are widely used in the informational battlefield, outer space exploration, rescue and relief work, and so on. In an online case, goals(targets) may arrive statistically with forced preorder constraints among them. The duration to execute a goal(target) and the probability of success to achieve a goal(target) may be time-dependent, both of which base on the start time of the execution. So if there are multi-unmanned vehicles that need to be collaboratively planned and scheduled online to handle the statistical incoming goals(targets) with time sensitiveness, a more efficient online planning and scheduling system need to be constructed to generate the global optimal plan in real time to achieve each arrived goal. As to construct the online system, the following problems should be firstly considered. How to use the PDDL(Planning Domain Description Language) to model a real world problem with multi-collaborated unmanned vehicles? How to efficiently search the planning solution for the planning problem with forced preorder constraints among the different goals?How to return the global optimal online planning and scheduling scheme in the time-dependent uncertain environment? In order to complete the above works, the main contributions of this paper are the followings.(1) Construct a OR(Operational Research) model to formalize the planning and scheduling problem in the off-line case, propose the architecture of the online planning and scheduling system, and discuss how to mode a real world problem by PDDL.Through the off-line OR model, the detailed feature and complexity of the problem are discussed. Then, considering the advantages of both AI planning and OR scheduling, an online system framework, which is a combination of intelligent planning and optimization scheduling, is proposed. An example about the air defense of warship is discussed to illustrate how to use the PDDL to model a real world planning problem,based on which the AI planning algorithm can be implemented. Then, based on the air defense case of a warship, the online planning and scheduling process proposed in this paper is discussed. Moreove, a simulation platform for the air defense of warship(s) is developed.(2) The deadlock checking and multi-step forward search algorithm are proposed to solve the planning problem with forced preorder constraints among the different goals in the initial state. For this planning problem, no matter which approach is adopted to achieve an atomic goal, all the atomic goals should be achieved in a given sequence.Otherwise, the planning may arrive at a dead-end., form which there is no way to the goal state. Many existing methods cannot detect the forced preorder constraintsaccurately, and thus the undiscovered forced preorder constraints may cause the forward-search to suffer from deadlocks. In this paper, we put forward an approach via an effective search heuristic to constrain a planner to satisfy the forced preorder constraints. We make use of an atomic goal-achievement graph(AGAG) in a look-ahead search under the forced preorder constraints. This allows a forward-search strategy to plan forward efficiently in multiple steps towards a goal state along a search path. Experimental results illustrate that, by avoiding deadlocks, we can solve more benchmark planning problems more efficiently than previous approaches.(3) Gives a new planning problem, and a novel forward search algorithm is proposed which can solve this new planning problem efficiently. For the new planning problem, there is no forced preorder constraint among the goals in the initial state. Any atomic goal which is firstly achieved starting from the initial state would not lead the search to a deadlock. However, as there are excludable constraints between the goal achievement operations of the different goals, selecting certain goal achievement operation to achieve a goal might introduce forced preorder constraints into the later planning process. In this paper, after discussing the detailed feature and the solving complexity of the problem, an excludable goal achievement operation set based multi-step forward search(Ex_Ms FS) algorithm is proposed, which is an extension of the deadlock checking algorithm. Several formal properties of Ex_Ms FS are proposed and an air defense of naval group based planning problems is adopted for the evaluation.Ex_Ms FS has a significant better performance than current planners as FF, SGPlan6 and LAMA-08.(4) Propose a re-planning based online planning optimizing method. During the online process, goals may arrive statistically and the probability of success to achieve a goal is uncertain. So it is hard to generate a global optimal solution. In this paper, as to get a more optimizing global planning solution, the re-planning strategy is sdopted to optimize the generated but un-executed planning in real time. The re-planning process takes the following issues into account: the continuous status changing of the objects during the planning and scheduling process, the different probability of success along with the different starting times of an execution. With the temporal constraints, the re-planning process returns the best current solution in real time. Based on the air defense process of a warship, an on-line simulation system is designed to confirm that,comparing with the un-re-planning, the re-planning strategy can improve the survival probability of the warship dramatically. In addition, the more time that is spent for the re-planning process, the much survival probability that is improved for the warship.(5) Contribute to introduce the start time-dependent probability of success into the online multi-unmanned vehicle planning and scheduling process and propose a PCL-DEC-MDP(Potential Chance Lost-Decentralized Markov Decision Processes)model to handle it. For this novel problem, there is no re-planning, and the success of aprocessing is expressed as a function of the time at which the processing is started.Compared with classic researches about online scheduling, extra trade-offs need to be considered in view of obtaining a high expectation value of completing current goal while lost less potential chance that should have handled a later arrived goal during its current processing. Simulation experiments abstracted from a naval group air-defense scenario shows that, the PCL-DEC-MDP based online planning algorithm is more likely to get a global optimal solution than that of DEC-MDP which does not take the potential chance lost into account. |
PDF Full Text Request