Examples of Simple Problem Solving Using CCM

Introduction

CCM is a model for symbol processing by randomized method only using local information. A program using CCM consists of production rules (only one rule in typical cases such as below) and local evaluation functions. Both of them are computed only using local data (or only a few number of data). CCM is similar to Genetic Algorithms in some sense. In the pages below, several examples using Java are shown.

This page and the pages linked from here contain explanation for experts. If you are not interested in the detail, try only the examples (links with smiley ()). (Note that the methods used here are not the standard methods for solving these problems.)

Examples Using Java

Constraint satisfaction problems (CSPs) are suited for CCM. Three (plus one) CSPs are shown for examples.

The N queens problem and sorting

Solutions of the N queens can be computed and N data can be sorted using the same rule but using different local evaluation functions. This page contains an applet that solves these problems.

Coloring of maps and graph vertices

The USA mainland map is colored using four colors for example.

Magic Squares

Magic squares are found using CCM.

A computational language called SOOC, which is based on CCM, has been developed on the top of Lisp. As explained in the introduction, types of programs can be easily expressed as a combination of production rules and local evaluation functions. However, SOOC has not yet transplanted to Java. So, the above programs are ``hand-compiled'' into Java functions in the above programs.

I have tested the Java applets, which are linked from the above pages, both on Netscape Navigator 3.0 and on Internet Explorer 3.0 on Windows 95, and on several other clients. However, they are not necessarily work correctly on clients on Macintosh. I am sorry if your client does not work well (_o_)

References

See a link collection on CCM. There are two reference lists. One is a list ordered in reverse time order and a list sorted by the types of problems, which can also be accessed indirectly through the first link collection. There is also a list of papers, which also contains papers on other researches (which is available only in Japanese currently). You can choose which you think the best.

Most of the papers in the above lists are accessed in PostScript format on the Internet. However, the following papers are in HTML, so you can directly see them using Web browsers.

• Kanada, Y., and Hirokawa, M.: Stochastic Problem Solving by Local Computation based on Self-organization Paradigm, 27th Hawaii International Conference on System Sciences (HICSS-27), 82-91, 1994.
• Yasusi Kanada : Toward A Model of Self-organizing Systems Using Computers, Proc. 33rd Programming Symposium, January, 1992 (in Japanese)
• Yasusi Kanada : Computational Systems as Self-organizing Systems -- Two Proposal for Software Research --, Proc. of the Summer Programming Symposium, July, 1992 (in Japanese).

The most recent paper in English is

• Y. Kanada: Methods of Parallel Processing of Constraint Satisfaction Using CCM --- A Model for Emergent Computation, SIG PPAI, Japan Society for Artificial Intelligence, Feb, 1996.

CCM was deviced in Central Research Laboratory, Hitachi, Ltd., which the author still belongs, and developed in Tsukuba Research Center, Real World Computing Partnership. However, the applets above are not developed in my organizational job. So, the copyright belongs to the author himself. You can copy or rewrite the applets freely unless commercial purpose.

This page was advertized by search engines and directory services using these messages.