A genetic algorithm approach for the object-sorting task problem

Author

Lin, Fang-Chang ; Hsu, Jane Yung-jen

Author_Institution

Dept. of Comput. Sci. & Inf. Eng., Nat. Taiwan Univ., Taipei, Taiwan

Volume

1

fYear

1995

fDate

22-25 Oct 1995

Firstpage

241

Abstract

Most multi-agent tasks have high complexity. Optimal solutions of them are nearly intractable because of the large complexity. One approach is to use stochastic search techniques such as genetic algorithms to explore the solutions by its implicit parallelism and genetic mechanism. This paper analyzes the complexity of the object-sorting task, shows its NP-completeness, and develops a genetic algorithm to explore the optima. Experimental results show that 1) GA can find an optimal solution quickly for simple problem instances. 2) The results are better than our previous proposed cooperation protocol approach. In addition, the results can serve as a reference foundation of OST to the other approaches

Keywords

computational complexity; cooperative systems; genetic algorithms; operations research; NP-completeness; cooperation protocol; genetic algorithm; implicit parallelism; multi-agent tasks; object-sorting task problem; stochastic search techniques; Computer science; Concrete; Genetic algorithms; Multiagent systems; Parallel processing; Protocols; Robots; Sorting; Space exploration; Stochastic processes;

fLanguage

English

Publisher

ieee

Conference_Titel

Systems, Man and Cybernetics, 1995. Intelligent Systems for the 21st Century., IEEE International Conference on

Conference_Location

Vancouver, BC

Print_ISBN

0-7803-2559-1

Type

conf

DOI

10.1109/ICSMC.1995.537765

Filename

537765