Context-aware multi-stage routing

ABSTRACT

In context-aware route planning, a set of agents has to plan routes on a common infrastructure and each agent has to plan a conflict-free route from a source to a destination without invalidating plans made by other agents. The existence of such a conflict-free set of plans can be ensured if each agent is allowed to reserve time slots on the infrastructure resources it intends to use.

In the multi-stage variant of the context-aware routing problem, each agent has a sequence of destination locations it must visit. A naive approach to solve the multi-stage variant is to make context-aware route plans between every two subsequent locations in the sequence, and then to concatenate these plans together. It can easily be shown, however, that this concatenation approach cannot guarantee that a multi-stage plan (if it exists) can always be found, and even if it is found, then it need not be optimal. Therefore, we present a new polynomial-time algorithm for the multi-stage routing problem that always returns the optimal (shortest-time) route for a single agent, given a set of reservations made by previous agents, thus providing a set of Pareto-optimal route plans.

Obviously, the need for such a dedicated multi-stage routing algorithm depends on the frequency with which the concatenation approach fails to find a plan, or finds a rather inefficient one. Our experiments show that, given a set of reservations from 200 agents, the concatenation approach fails to find a solution in more than 50% of the cases, for random visiting sequences of six locations or more. However, if the concatenation approach does find a solution, its plan quality is often close to that of an optimal solution.

REFERENCES

• 1: James F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM, v.26 n.11, p.832-843, Nov. 1983 [doi>10.1145/182.358434]
• 2: G. Bruno, G. Ghiani, and G. Improta. Dynamic positioning of idle automated guided vehicles. Journal of Intelligent Manufacturing, 11(2):209--215, April 2000.
• 3: Rina Dechter , Judea Pearl, Generalized best-first search strategies and the optimality of A*, Journal of the ACM (JACM), v.32 n.3, p.505-536, July 1985 [doi>10.1145/3828.3830]
• 4: P. E. Hart, N. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics SSC4, 4(2):100--107, 1968.
• 5: W. Hatzack and B. Nebel. The operational traffic problem: Computational complexity and solutions. In A. Cesta, editor, Proceedings of the 6^th European Conference on Planning (ECP'01), pages 49--60, 2001.
• 6: C. W. Kim and J. Tanchoco. Conflict-free shortest-time bidirectional AGV routeing. International Journal of Production Research, 29(1):2377--2391, 1991.
• 7: Y. Kim, T. Suzuki, and T. Narikiyo. Fms scheduling based on timed petri net model and reactive graph search. Applied mathematical modelling, 31(6):955--970, 2007.
• 8: J. Lin and P.-K. Dgen. An algorithm for routeing control of a tandem automated guided vehicle system. International Journal of Production Research, 32(12):2735--2750, December 1994.
• 9: Samia Maza , Pierre Castagna, A performance-based structural policy for conflict-free routing of bi-directional automated guided vehicles, Computers in Industry, v.56 n.7, p.719-733, September 2005 [doi>10.1016/j.compind.2005.03.003]
• 10: John H. Reif, Complexity of the mover's problem and generalizations, Proceedings of the 20th Annual Symposium on Foundations of Computer Science, p.421-427, October 29-31, 1979
• 11: Yoav Shoham , Moshe Tennenholtz, On social laws for artificial agent societies: off-line design, Artificial Intelligence, v.73 n.1-2, p.231-252, Feb. 1995 [doi>10.1016/0004-3702(94)00007-N]
• 12: F. Taghaboni-Dutta and J. Tanchoco. Comparison of dynamic routing techniques for automated guided vehicle system. International Journal of Production Research, 33(10):2653--2669, 1995.
• 13: Adriaan ter Mors , Xiaoyu Mao , Jonne Zutt , Cees Witteveen , Nico Roos, Robust Reservation-Based Multi-Agent Routing, Proceeding of the 2008 conference on ECAI 2008: 18th European Conference on Artificial Intelligence, p.929-930, June 27, 2008
• 14: A. W. ter Mors, J. Zutt, and C. Witteveen. Context-aware logistic routing and scheduling. In Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling, pages 328--335, 2007.
• 15: I. F. Vis. Survey of research in the design and control of automated guided vehicle systems. European Journal of Operational Research, 170(3):677--709, May 2006.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Algorithms

Keywords:
agents, multi-stage routing