A Multi-Objective Incremental Path Planning Algorithm for Mobile Agents


Oral T., POLAT F.

11th IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT), Macau, Çin, 4 - 07 Aralık 2012, ss.401-408 identifier identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Doi Numarası: 10.1109/wi-iat.2012.143
  • Basıldığı Şehir: Macau
  • Basıldığı Ülke: Çin
  • Sayfa Sayıları: ss.401-408
  • Anahtar Kelimeler: Path planning, multi-objectivity, incremental search algorithm
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

Path planning is a crucial issue in unknown environments where an autonomous mobile agent has to reach a particular destination from some initial location. There are several incremental algorithms such as D-star[1], D-star Lite [2] that are able to ensure reasonable paths in terms of path length in unknown environments. However, in many real-world problems we realize that path length is not only the sole objective. For example in computer games, a non-player character needs to not only find a minimum cost path to some target location but also minimize threat exposure. This means that path planning/finding activity of an agent in a multi-agent environment has to consider more than one objective to be achieved. In this paper, we propose a new incremental search algorithm called MOD star Lite extending Koenig's D-star Lite algorithm and show that MOD* Lite is able to optimize path quality in more than one criteria that cannot be transformed to each other. Experimental results show that MOD* Lite is able to find optimal solutions and is fast enough to be used in real-world multi-agent applications such as robotics, computer games, or virtual simulations.