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.
| Original language | English |
|---|---|
| Pages (from-to) | 241-246 |
| Number of pages | 6 |
| Journal | Proceedings of the IEEE International Conference on Systems, Man and Cybernetics |
| Volume | 1 |
| State | Published - 1995 |
| Externally published | Yes |
| Event | Proceedings of the 1995 IEEE International Conference on Systems, Man and Cybernetics. Part 2 (of 5) - Vancouver, BC, Can Duration: 22 10 1995 → 25 10 1995 |