Fast transformation of temporal plans for efficient execution

摘要: Temporal plans permit significant flexibility in specifying the occurrence time of events. Plan execution can make good use that flexibility. However, advantage is counterbalanced by cost during propagating events throughout flexible plan. To minimize latency, this propagation needs to be very efficient. Previous work showed every temporal plan reformulated as a dispatchable plan, Le., one for which immediate neighbors sufficient. A simple algorithm was given finds with minimum number edges cubic and quadratic space. In paper, we focus on efficiency reformulation process, improve result. new presented uses linear space has complexity equivalent Johnson's all-pairs shortest-path problems. Experimental evidence confirms practical effectiveness algorithm. For example, large commercial application, performance improved at least two orders magnitude. We further show already minimal total edges, also made maximum incoming or outgoing any node.