A new algorithm for generation of dispatchable networks with temporal constraints. Issue 7 (9th August 2017)

• Record Type: Journal Article
• Authors: Chen, Dexiang; Xu, Rui; Cui, Pingyuan; Zhu, Shengying; Li, Zhaoyu
• Is Part Of: Enterprise information systems. Volume 11:Issue 7(2017)
• Page Start: 1005
• Page End: 1017
• Publication Date: 2017-08-09
• Subjects: Mission planning -- temporal constraint -- Simple Temporal Network -- dispatchable execution -- partial path consistency (PPC); Information storage and retrieval systems -- Periodicals; Management information systems -- Periodicals; Electronic commerce -- Periodicals; 658.4038011
• DOI: 10.1080/17517575.2016.1161241
• Languages: English
• ISSNs: 1751-7575

Abstract

ABSTRACT: In most real-world planning domains, it is important to have flexible executive time against uncertainty and disturbance of environment. Execution time can be propagated from dispatchable Simple Temporal Network (STN), which is obtained from filtering the distance graph of STN. To minimise the execution latency, computation of dispatchable STN should be improved. In the previous works, all-pairs shortest paths (APSP) algorithm is used to compute distance graph of STN, so the redundant constraints should be processed in the following filtering process. In this paper, an improved algorithm named Dispatchabile Partial Path (DPP) algorithm, which uses the P 3 C algorithm to replace APSP and compute the shortest distance of vertices, is presented. To ensure the correctness of dispatchable STN, triangulation uses vertices ordering sorted by execute time. The filtering process is also simplified by time-sorting vertices. Experimental evidence confirms that the DPP algorithm outperforms previous algorithms based on APSP.