Font Size: a A A

Research On Temporal Representation And Conflict Resolution Of Action Plan Based On STN

Posted on:2011-08-12Degree:MasterType:Thesis
Country:ChinaCandidate:L H TangFull Text:PDF
GTID:2166330338489846Subject:Management Science and Engineering
Abstract/Summary:PDF Full Text Request
Time is a critical element of military actions,temporal consistency is closely related with success of military plans.Especially at the age of information,the rhythm of war has speeded a lot,which demands more time precision.Military plans always contain lots of complex temporal constraints,for instance, sequence,synchronization,deadline,and so on.The satisfaction of these constraints is a indispensable condition for the success of military actions ,thus it's necessary to represent and reason these constraints effectively. STN is a constraint-based method of temporal representation and reasoning,which can express complex temporal relations,and have the advantage of computing convenience,so it's uesed in the field of planning and scheduling widely.Temporal consistency of acion plans can be judged through STN consistency checking, however, existed algorithms have a comman disadvantage:they can only detect conflicts but can't resolve them,the workload of conflicts resolution are all undertaked by the planner. In the phase of plan establishment,temporal conflicts always appear due to the illogical setting by planners,in the phase of plan execution ,temporal conflict can be induced by execution abnormity.As a result,it's not reasonable or even feasible to merely rely on a planner to deal with all of such conflicts.This thesis focuses on the problem of temporal conflict management of action plans. To ensure the temporal consitency of plan we use STN to express the temporal constraints and proposed both static and dynamic method of temporal conflict detection and resolution.The work of this thesis can be summarised as follows:1,Provided a method of STN construction for a action planTo represent and reason temporal constraints of a plan,a STN should be constructed.First,we gain a qualitative temporal network based on four kinds of basic processes.Afterwards, we transform qualitative constraints to quantitative constraints based on three transformation rules.Last,through adding other complex quantitative constriants we construct a STN.These work establishes the precondition for works in the next chapters.2,Proposed an algorithm of static temporal conflicts detection and resolution.To solve conflicts appearing in the phase of plan establisment,we proposed CDR algorithm,which detects a conflict and then rosolve it,this process repeats iteratively until all the constraints can be satisfied.A cost-based method of conflict resolution is proposed ,and we adapt the negative cycle detection algorithm to work incrementally, which can reduce unnecessary computation and improve the efficiency of the algorithmn.CDR algorhimn can resolve all the conflicts in polynomial time ,and we illustrated that it's more efficient compared with two other algorithms by experiments. 3,Proposed a mehod to resolve dynamic temporal conflicts in the phase of plan executionWe analysed two kinds of conflicts induced by events lag or ahead of schedule, gave the definition of dynamic temporal conflict and proposed the theorem of conflict detection,To resolve the conflicts,we designed a conflict route search algorithm based on DFS and backtracking,and proposed two methods according to different conditions :the first one established a cost model and calculate accurate adaptation of constraints ,while the second one only provide a heuristic to remind the planner to take the adaption order into account.This process can detect and resolve conflict dynamincally, thus ensuring temporal consistency in the phase of plan execution.
Keywords/Search Tags:simple temporal network, acion plan, temporal consistency, conflict detection and resolution
PDF Full Text Request
Related items