Detail publikace

Canadian traveller problem: A note about Game Theory approach

HRDINA, J. MATOUŠEK, R.

Anglický název

Canadian traveller problem: A note about Game Theory approach

Typ

článek v časopise ve Scopus, Jsc

Jazyk

en

Originální abstrakt

In a variety of real world problems from robot navigation to logistics, agents face the challenge of path optimization on a graph with unknown edge costs. It is known as the Canadian Traveller Problem (CTP). There are many variants of CTP and many path planning approaches to find an optimal solution of the CTP. The aim of the paper is to present the possible way for a solution strategy and possible problem description by means of the Game Theory (GT). The paper presents initial study and theoretical background of the Game Theory approaches to find a proper CTP policy. In this problem the agent known as a traveller needs to go trough the real-life ways implemented by CTP. The presented CTP problem is a base problem with unrecoverable edges. Because the most of the CTP solution strategies are based on heuristic and meta-heuristic algorithms, i.e. on the ground of Artificial Intelligence (AI) approaches, we also present this kind of solution. The GT solution is compared with advance swarm intelligence strategy based on Elitist Ant System (AS).

Anglický abstrakt

In a variety of real world problems from robot navigation to logistics, agents face the challenge of path optimization on a graph with unknown edge costs. It is known as the Canadian Traveller Problem (CTP). There are many variants of CTP and many path planning approaches to find an optimal solution of the CTP. The aim of the paper is to present the possible way for a solution strategy and possible problem description by means of the Game Theory (GT). The paper presents initial study and theoretical background of the Game Theory approaches to find a proper CTP policy. In this problem the agent known as a traveller needs to go trough the real-life ways implemented by CTP. The presented CTP problem is a base problem with unrecoverable edges. Because the most of the CTP solution strategies are based on heuristic and meta-heuristic algorithms, i.e. on the ground of Artificial Intelligence (AI) approaches, we also present this kind of solution. The GT solution is compared with advance swarm intelligence strategy based on Elitist Ant System (AS).

Klíčová slova anglicky

Ant System; Canadian Traveller Problem; CTP; Game Theory; Swarm intelligence

Rok RIV

2014

Vydáno

01.09.2014

Nakladatel

Brno University of Technology

Místo

Brno

ISSN

1803-3814

Ročník

2014

Číslo

1

Strany od–do

403–406

Počet stran

4

BIBTEX


@article{BUT132900,
  author="Jaroslav {Hrdina} and Radomil {Matoušek},
  title="Canadian traveller problem: A note about Game Theory approach",
  year="2014",
  volume="2014",
  number="1",
  month="September",
  pages="403--406",
  publisher=" Brno University of Technology",
  address="Brno",
  issn="1803-3814"
}