Evolving EFSMs solving a path-planning problem by genetic programming

Maxim Buzdalov; Andriy Sokolov

doi:10.1145/2330784.2330880

Evolving EFSMs solving a path-planning problem by genetic programming

Maxim Buzdalov
, Andriy Sokolov

ITMO University

Research output: Chapter in Book/Report/Conference proceeding › Conference Proceeding (ISBN)

1 Citation (Scopus)

Abstract

In this paper, we present an approach to evolving of an algorithm encoded as an extended finite-state machine that solves a simple path-planning problem - finding a path in an unknown area filled with obstacles using a constant amount of memory - by means of genetic programming. Experiments show that in 100% of cases a reasonably correct EFSM with behavior similar to one of the BUG algorithms is evolved.

Original language	English
Title of host publication	GECCO '12
Subtitle of host publication	Proceedings of the 14th annual conference companion on Genetic and evolutionary computation
Editors	Terence Soule
Publisher	Association for Computing Machinery
Pages	591-594
Number of pages	4
ISBN (Electronic)	978-1-4503-1178-6
DOIs	https://doi.org/10.1145/2330784.2330880
Publication status	Published - 07 Jul 2012
Externally published	Yes
Event	GECCO 2012 - Genetic and Evolutionary Computation Conference - Philadelphia, United States of America Duration: 07 Jul 2012 → 11 Jul 2012

Conference

Conference	GECCO 2012 - Genetic and Evolutionary Computation Conference
Country/Territory	United States of America
City	Philadelphia
Period	07 Jul 2012 → 11 Jul 2012

Keywords

bug algoritms
finite-state machine
genetic programming
path-planning problem

Access to Document

10.1145/2330784.2330880

Permanent link

Persistent link

Cite this

@inproceedings{bf8997452fe94f40b5ddb92e6217b9ff,

title = "Evolving EFSMs solving a path-planning problem by genetic programming",

abstract = "In this paper, we present an approach to evolving of an algorithm encoded as an extended finite-state machine that solves a simple path-planning problem - finding a path in an unknown area filled with obstacles using a constant amount of memory - by means of genetic programming. Experiments show that in 100\% of cases a reasonably correct EFSM with behavior similar to one of the BUG algorithms is evolved.",

keywords = "bug algoritms, finite-state machine, genetic programming, path-planning problem",

author = "Maxim Buzdalov and Andriy Sokolov",

year = "2012",

month = jul,

day = "7",

doi = "10.1145/2330784.2330880",

language = "English",

pages = "591--594",

editor = "Terence Soule",

booktitle = "GECCO '12",

publisher = "Association for Computing Machinery",

address = "United States of America",

note = "GECCO 2012 - Genetic and Evolutionary Computation Conference ; Conference date: 07-07-2012 Through 11-07-2012",

}

Buzdalov, M & Sokolov, A 2012, Evolving EFSMs solving a path-planning problem by genetic programming. in T Soule (ed.), GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computation. Association for Computing Machinery, pp. 591-594, GECCO 2012 - Genetic and Evolutionary Computation Conference, Philadelphia, Pennsylvania, United States of America, 07 Jul 2012. https://doi.org/10.1145/2330784.2330880

Evolving EFSMs solving a path-planning problem by genetic programming. / Buzdalov, Maxim; Sokolov, Andriy.
GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computation. ed. / Terence Soule. Association for Computing Machinery, 2012. p. 591-594.

Research output: Chapter in Book/Report/Conference proceeding › Conference Proceeding (ISBN)

TY - GEN

T1 - Evolving EFSMs solving a path-planning problem by genetic programming

AU - Buzdalov, Maxim

AU - Sokolov, Andriy

PY - 2012/7/7

Y1 - 2012/7/7

N2 - In this paper, we present an approach to evolving of an algorithm encoded as an extended finite-state machine that solves a simple path-planning problem - finding a path in an unknown area filled with obstacles using a constant amount of memory - by means of genetic programming. Experiments show that in 100% of cases a reasonably correct EFSM with behavior similar to one of the BUG algorithms is evolved.

AB - In this paper, we present an approach to evolving of an algorithm encoded as an extended finite-state machine that solves a simple path-planning problem - finding a path in an unknown area filled with obstacles using a constant amount of memory - by means of genetic programming. Experiments show that in 100% of cases a reasonably correct EFSM with behavior similar to one of the BUG algorithms is evolved.

KW - bug algoritms

KW - finite-state machine

KW - genetic programming

KW - path-planning problem

UR - https://www.scopus.com/pages/publications/84865021331

U2 - 10.1145/2330784.2330880

DO - 10.1145/2330784.2330880

M3 - Conference Proceeding (ISBN)

SP - 591

EP - 594

BT - GECCO '12

A2 - Soule, Terence

PB - Association for Computing Machinery

T2 - GECCO 2012 - Genetic and Evolutionary Computation Conference

Y2 - 7 July 2012 through 11 July 2012

ER -

Evolving EFSMs solving a path-planning problem by genetic programming

Abstract

Conference

Keywords

Access to Document

Permanent link

Other files and links

Fingerprint

Cite this