Kanada's papers

Kanada, Y., 33rd Programming Symposium, Information Processing Society of Japan, 1992, Published by IPSJ.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper in hypertext format (in Japanese) ]
[ Paper postscript file: Part 1, Part 2 (in Japanese)]
[ OHP postscript file ]
[ OHP PDF file ]

[ N queens problem and sort demo in Java ]

[No English abstract is available.]

[No English abstract is available.]

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., Summer Programming Symposium, Information Processing Society of Japan, 1992, Published by IPSJ.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper in hypertext format (in Japanese) ]
[ Paper postscript file: Part 1, Part 2 (in Japanese) ]
[ OHP postscript file ]

[No English abstract is available.]

[No English abstract is available.]

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., SICE 11th SIG Systems Engineering Note, The Society of Instrument and Control Engineers, pp. 27-34, 1993, Published by SICE.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file: Part 1, Part 2 (in Japanese) ]
[ OHP postscript file: Slides, Handout ]
[ OHP PDF file: Slides, Handout ]

[No English abstract is available.]

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., and Hirokawa, M.: , SIG Notes of Symbol Processing, Information Processing Society of Japan, 93-SYM-68-2, 1993, Published by IPSJ.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file (in Japanese) ]
[ OHP postscript file: Slides, Handout ]
[ OHP PDF ファイル: Slides, Handout ]

[ N queens problem demo in Java ]

Abstract: The authors have proposed the Chemical Casting Model (CCM), which is a computation model for self-organizing computation. In this model, "programs" consist of a few production rules and evaluation functions (or local order degrees), both of which only refer to local information. A method of solving certain constraint-satisfaction problems, based on this model, is presented in this paper. This method enables to solve constraint-satisfaction problems, such as the N-queens problems or map coloring problems, in a polynomial order time, without using deterministic and procedural constraint propagation, but using a stochastic method, and by a very simple "program." This paper also mentions to the characteristics of the computation by on this method, based on several measurements.

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., Technical Report of IEICE, COMP92-93 and SS92-40, The Institute of Electronics, Information and Communication Engineers, pp. 1-10, 1993, Published by IEICE.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file (in Japanese) ]
[ OHP postscript file: Slides, Handout ]
[ OHP PDF file: Slides, Handout ]

Abstract: Systems, which perform complex symbol processing, can neigher be understood by understanding the program statically nor by tracking their microscopic behavior. Thus, macroscopic models of the computation processes are necessary to understand the systems. Macroscopic models are also necessary for automatic control of computation and realizing self-organizing computation. This paper examines foundation of macroscopic theory of computation processes, and proposes modeling based on stochastic process theory. This paper also gives an example of a macroscopic model, the Markov chain model of the Chemical Casting Model (CCM), which is a microscopic model, and analizes computation processes of a graph coloring problem based on CCM. This theory realizes a fusion of symbol computation in the microscopic model and pattern computation in the macroscopic model.

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., Bussei Kenkyu, February, 1994, Published by IPSJ.


[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file (in Japanese) ]
[ Poster postscript file: Poster, Handout ]
[ Poster PDF file: Poster, Handout ]

[English abstract is not available.]

Presented in August 1993.

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., SWoPP '93 (SIG Notes of Artificial Intelligence), Information Processing Society of Japan, 93-AI-89-2, 11-20, 1993, Published by IPSJ.

[ 日本語のページ ]
[ Paper Update 3 PDF file (in Japanese) ] [ Paper Update 3 postscript file (in Japanese) ]
[ OHP postscript file: Slides, Handout ]
[ OHP PDF file: Slides, Handout ]

[ Coloring demo in Java ]

Abstract: Problem-solving, such as constraint satisfaction or optimization, can be viewed as solution search. Conventional solution search methods in Artificial Intelligence and Operations Research are based on exhaustive and systematic search on tree-structured search space using backtrack. The author proposed a computation model called CCM (Chemical Casting Model), which is based on production rules and local evaluation functions that work in a decentralized and parallel manner, in recent papers. Solution search using CCM can be regarded as random walk on search space, biased by evaluation functions. Several features of this method are that it searches on strongly-connected graphs, that reversible and symmetric rules are used, and that the strength of bias and the locality of rules can be changed by adding or removing so-called catalysts in rules or by composing rules.

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., 47th National Conference, Information Processing Society of Japan, pp. 1-99-100, 1993, Published by IPSJ.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file: Part 1, Part 2 (in Japanese) ]
[ OHP postscript file: Slides, Handout ]
[ OHP PDF file: Slides, handout ]

Abstract: The author proposed a computation model called Chemical Casting Model (CCM), which is targeted self-organizing computation based on local and partial information. In CCM, a program consists of production rules and evaluation functions that are computed with local information. CCM is applied to 0-1 Knapsack Problems, but near optimal solutions can not be found using a simple program without new mechanisms or with simulated annealing when n > 20. However, optimal solutions are found by the probability of 37% or more using the same rule with rule composition method. If the rule composition is automated, optimal solutions are found by a high probability using very simple rules and evaluation functions only.

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., SIG Notes on Symbol Processing, Information Processing Society of Japan, 93-SYM-71-5, pp. 33-40, 1993, Published by IPSJ

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file (in Japanese) ]
[ OHP postscript file: Slides, Handout ]
[ OHP PDF file: Slides, Handout ]

[ Sort and N queens problem demo in Java (Only one type of sorting) ]

Abstract: The author has proposed the Chemical Casting Model (CCM), which is a stochastic computation model whose elements are production rules and evaluation functions that are computed only using local information, and has proposed a computation language SOOC based on CCM. This model is targeted to apply to problems on open systems in which even specifications cannot be clearly written down. However, it is also important to make experiment on applying this model to conventional problems. Thus, CCM is applied to sorting in this paper, and a new sorting method is presented and several sorting methods based on conventional methods, i.e., insertion sort and exchange sort, are presented. The results of experiments are also shown. By these methods, sorting can be done only using one production rule and one evaluation function both of which only refer to local information. Several interesting phenomena caused by computation only using local information are also mentioned.

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., and Hirokawa, M., 27th Hawaii International Conference on System Sciences (HICSS-27), 82-91, 1994.

[ 日本語のページ ]
[ Paper PDF file, (C) Copyright by IEEE ]
[ Paper in hypertext format (Figures are not available now) ]
[ Paper postscript file, (C) Copyright by IEEE ]
[ OHP postscript file: Slides, Handout ] [ OHP PDF file: Slides, Handout ]
[ IEEExplore Paper page ]

[ N queens problem and sort demo in Java ]

Abstract: We are developing a new problem-solving methodology based on a self-organization paradigm. To realize our future goal of self-organizing computational systems, we have to study computation based on local information and its emergent behavior, which are considered essential in self-organizing systems. This paper presents a stochastic (or nondeterministic) problem solving method using local operations and local evaluation functions. Several constraint satisfaction problems are solved and approximate solutions of several optimization problem are found by this method in polynomial order time in average.

Major features of this method are as follows. Problems can be solved using one or a few simple production rules and evaluation functions, both of which work locally, i.e., on a small number of objects. Local maxima of the sum of evaluation function values can sometimes be avoided. Limit cycles of execution can also be avoided. There are two methods for changing the locality of rules. The efficiency of searches and the possibility of falling into local maxima can be controlled by changing the locality.

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., SIG Note of Parallel Procesing of Artificial Intelligence, The Society of Artificial Intelligence, SIG-PPAI-9401, pp. 7-12, 1994, Published by JSAI.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file: Part 1, Part 2 (in Japanese) ]
[ Poster postscript file: Part 1, Part 2 ]
[ Poster PDF file : Part 1, Part 2 ]

[ Coloring demo in Java (static coloring) ]

Abstract: Real world computing systems are complex systems that is open to the continually varying environment. Conventional software development methods inherently cannot deal such situations. CCM (Chemical Casting Model) is a model of nondeterministic, or random, computation, which is based on local information. CCM is developed toward establishing a software development methodology based on emergent computation. CCM is a production system with locally computed evaluation functions. A method of coloring vertices of dynamically changing graphs, or a method of radio-wave assignments to moving stations, by using SOOC -- a CCM-based computation language, is explained, and the results of experiments are shown in the present report. Dynamic coloring can be performed using the same production rule and evaluation function as static coloring, and the results can be evaluated using basically the same method and tools.

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., SICE 14th SIG Systems Engineering Note, The Society of Instrument and Control Engineers, 45-52, 1994, Published by SICE.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file: Part 1, Part 2 (in Japanese) ]

[English abstract is not available.]

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., Artificial Life IV, Poster, 1994.


[ 日本語のページ ]
[ Paper PDF file ] [ Poster in hypertext format (not yet available) ]
[ Unpublished extended paper PDF file ]

Abstract: Cellular automata are used as models of emergent computation and artificial life. They are usually simulated under synchronous and deterministic conditions. Thus, they are evolved without existence of noise, i.e., fluctuation or randomness. However, noise is unavoidable in real world. The objective of the present paper is to show the following two effects and several other effects caused by asynchronism or synchronism and by existence or nonexistence of randomness in the computation order in one-dimensional asynchronous cellular automata (1D-ACA) experimentally. One major effect is that certain properties of two-neighbor 1D-ACA are fully expressed in their patterns if certain level of randomness exists, though they are only partially expressed if no randomness exists. The patterns generated by 1D-ACA may have characteristics, such as mortality of domains of 1's or splitting domains of 0Us into two. These characteristics, which are coded in the RchromosomeS of the automata, i.e., the look-up table, are fully expressed only when the computation order is random. The other major effect is that phantom phenomena, which almost never occurs in real world, sometimes occur when there is no noise. The characteristics of patterns generated by several 1D-ACA are drastically changed from uniform patterns to patterns with multiple or chaotic phases when only low level of noise is added.

Reference: "Asynchronous cellular automaton", Wiki Pedia. The originality of this paper is briefly described.

Introduction to this research theme: RACA: Randomized Asynchronous Cellular Automata

Kanada, Y., SWoPP '94 (SIG Note of Artificial Intelligence, Information Processing Society of Japan), 94-AI-95-4, pp. 29-38, 1994, Published by IPSJ.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file (in Japanese) ]
[ OHP postscript file: Slides, Handout ] [ OHP PDF ファイル: Slides, Handout ]

[ Several constraint satisfaction problem demos in Java (You can change catalysts, rules, and frustration.) ]

Abstract: CCM (Chemical Casting Model) is a model of nondeterministic, or random, computation. CCM is developed toward establishing a problem solving methodology based on emergent computation, which is open to continually varying environment. Computation in CCM is based on local information. However, a solution cannot be found if the locality is at the limit. Thus, the locality of computation, especially computation of the evaluation functions, must be controlled properly, and the locality in the search space must be controlled properly not to fall into local optima. Four methods of controlling locality are shown in this report. They are addition or removal of catalysts, composition of reaction rules (or tunneling), simulated annealing (SA) and frustration accumulation method (FAM). We found that catalysts and FAM are effective in constraint satisfaction, but that the performance is worse than conventional methods when only using these methods in a case. We also found that tunneling, or dynamical composition of reaction rules, is effective in optimization.

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., SIG Note of Symbol Processing, Information Processing Society of Japan, 94-SYM-75-5, pp. 31-38, 1994, Published by IPSJ.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file (in Japanese) ]
[ OHP postscript: Slides, Handout ]
[ OHP PDF ファイル: Slides, Handout ]

[ Magic square demo in Java ]

Abstract: A computation model called CCM was proposed by the author. CCM is developed toward establishing a problem solving methodology based on emergent computation, which is open to continually varying environment. CCM is a production system with evaluation functions, which are computed using only local information, and CCM works randomly. A computational language called SOOC-94 is used for experiments based on CCM. The features and implementation of SOOC-94 are explained using the magic square problem as an example. The features of SOOC-94 are that the automatic computation of evaluation functions and automatic local backtracking are taken place when applying a rule, that the syntax of the patterns in LHS and RHS are almost unified, the existence of two scheduling strategies, especially the random strategy, on the order of rule applications, that the existence of same name elements in a datum (structure) is allowed, and so on.

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., not yet published, 1994.

[ 日本語のページ ]
[ Paper PDF file] [ Paper postscript file]

Abstract: Today's computer applications often require on-line input and output and sometimes requires change of computation methods while processing complex tasks. In future, they will probably be required to change even the objectives of computation. Such a new style of information processing is called real-world computing in the present paper. Real-world computing requires computation languages to work without fixed sequence of control nor fixed data flow, to work without a whole plan of computation, to be always open to environment at any time, to have possibility of distributed and parallel processing, to have possibility to respond to nondeterministic actions, and so on. Because today's programming languages are considered not to satisfy these requirements, a new computation model called CCM (chemical casting model) and a language called SOOC-94, which partially satisfies the requirements, are developed as the first step. Computation is regarded as biased random walk in CCM. The random walk is realized by a randomly acting forward-chaining production system, and the bias is realized by locally computed evaluation functions in SOOC-94. I have developed a preliminary version of compiler and interpreter, and analyzed the computation processes and results of graph coloring problems for example.

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., 49th National Conference, Information Processing Society of Japan, 4-321 - 322, 1994, Published by IPSJ.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file: Part 1, Part 2 (in Japanese) ]
[ OHP postscript file: Slides, Handout ] [ OHP PDF ファイル: Slides, Handout ]

Abstract: A computation model called CCM was proposed by the author. CCM is developed toward establishing a problem solving methodology based on emergent computation, which is open to continually varying environment. CCM is a production system with evaluation functions, which are computed using only local information, and CCM works randomly. A computational language called SOOC-94 is used for experiments based on CCM. The features and implementation of SOOC-94 are explained using the magic square problem as an example. The features of SOOC-94 are that the automatic computation of evaluation functions and automatic local backtracking are taken place when applying a rule, that the syntax of the patterns in LHS and RHS are almost unified, the existence of two scheduling strategies, especially the random strategy, on the order of rule applications, that the existence of same name elements in a datum (structure) is allowed, and so on.

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., 5th National Conference, Japan Neural Network Society, pp. 36-39, 1994, Published by JNNS.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file: Part 1, Part 2 (in Japanese) ]
[ OHP PDF file: Slides, Handout ] [ OHP postscript file: Slides, handout ]

Abstract: The basics of CCM (chemical casting model), which is a computation model for emergent computation, is explained, and an extension of CCM, i.e., dynamical composition of rules, is described. The relation between the extended CCM and neural networks, especially the neural networks with linked state transition, is mentioned, and the importance of designing good concrete dynamics is also mentioned.

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., not yet published, 1995.

[日本語のページ ]
[ Paper PDF file ] [ Paper postscript file ]

Abstract: A method of solving combinatorial problems, such as the N queens problem or graph coloring problems using independent parallel processes, is proposed in the present paper. This method is stochastic (or randomized). Problems are decomposed for parallel processing implicitly and stochastically by this method. This method is based on CCM, which is a computational model proposed by the author. A program consists of production rules and local evaluation functions in CCM. Each process uses the same set of rules and functions, and it may use the same set of initial data in this method. However, the performance is approximately in proportion to the number of processors in average in certain cases. The theoretical reason of this linear acceleration is explained, and several results of experiments, some of which was successful but others were not, are also shown.

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, K., Fuzz-IEEE/IFES '95, pp. 2319-2326, 1995.
[ 日本語のページ ]
[ Paper PDF file. (C) Copyright 1995 by IEEE]
[ Paper postscript file. (C) Copyright 1995 by IEEE]
[ IEEExplore Paper page ]

Abstract: A method of solving fuzzy constraint satisfaction problems defined by Ruttkay is shown in the present paper. This method is based on CCM, which is a computation model for emergent computation or for locality-based problem solving. CCM is a type of production system. It works stochastically, or randomly, and works with evaluation functions that are computed only with local information. CCM has been applied to constraint satisfaction problems (CSPs). Binary-valued evaluation functions, each of which indicates whether a constraint is satisfied, are used. If the values of evaluation functions are extended to real values, fuzzy CSPs can be expressed in CCM, and solved using a technique similar to GSAT or annealing. This method is applied to a fuzzy graph coloring problem, and the performance is evaluated. This method can also be applied to an open and dynamical fuzzy/non-fuzzy CSPs, in which data and constraints are changing dynamically or coming from or going to the outside of the system.

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., SWoPP '95 (SIG Note of Artificial Intelligence, Information Processing Society of Japan), AI95-16, pp. 17-24, 1995, Published by IPSJ

[ 日本語のページ ]
[ Paper postscript file]

Abstract: A method for solving large-scale constraint satisfaction problems based on CCM (Chemical Casting Model), which is a model for emergent computation, is proposed in this report. A parallelized version of this method is also shown. Large-scale problems could not be solved using CCM. However, this report shows that, by introducing a method of annealing called FAM (Frustration Accumulation Method) and by adjusting the parameters appropriately, several large-scale graph coloring problems has become solvable with spending the same order of time as GSAT or simulated annealing by sequential processing using CCM. This report also shows that this method can easily be parallelized with restricted amount of mutual exclusion. The performance is almost proportional to the number of processors under certain conditions.

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., IEEE Systems, Man and Cybernetics '95, (C) Copyright 1995 by IEEE.
[ 日本語のページ ]
[ Paper PDF file] [ Paper postscript file]
[ IEEExplore Paper page ]

Abstract : Levy and Montalvo, Yao, and Shima individually pro-posed tunneling algorithms. The tunneling algorithms employ analogy to tunnel effect in physics, and are used to optimize continuous systems. The present paper proposes a method of solving combinatorial problems using a type of randomized dynamic tunneling technique. This method is based on a computational model called CCM*. CCM* is an extended version of the Chemical Casting Model (CCM). CCM was proposed by the author toward developing a method of solving open and incompletely-specified problems that may change while being solved, using self-organizing computation.

The 0-1 integer programming problem is solved using CCM* with a very simple rule and an evaluation function. CCM* allows us to escape from local maxima by composing the rule dynamically and randomly. This cannot be done by using the original production rule as is. Our experiments show that approximate solutions can be found more rapidly by CCM* than by using a branch-and-bound method in the case of 0-1 integer programming.

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., 1995 Int'l Conference on Evolutionary Computation (ICEC '95), pp. 467-472, (C) Copyright 1995 by IEEE.

[ 日本語のページ ]
[ Paper PDF file] [ Paper postscript file]
[ IEEExplore Paper page ]

Abstract : The present paper proposes a method of solving combinatorial problems using randomized dynamic rule composition. This method is called CCM* and is based on a computational model called Chemical Casting Model (CCM), which is a rule-based computational model for emergent computation. CCM was proposed by the author toward solving dynamic, open and incompletely specified problems using a few simple rules and evaluation functions. By composing a rule from a given production rule dynamically and randomly, CCM* makes it possible to escape from local maxima, which cannot be escaped from by applying the original rule. This method is compared with the original CCM and another extended version of CCM, i.e., CCM with simulated annealing. 0-1 integer programming problems are solved using these methods. Our experiments show that CCM* performs much better than both the original and annealed CCM. In addi-tion, suboptimal solutions can be found in less time than a branch-and-bound method.

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., not yet published, 1996.

[ 日本語のページ ]
[ Paper PDF file ] [ Paper postscript file ]

Abstract: A method for solving large-scale constraint satisfaction problems using an annealed symmetrically-connected neural network, which is called DSN-FAM, is proposed in the present paper. Some conventional methods, such as Hopfield networks, often fail to find a solution. Some others, such as Boltzmann Machines, take too much time. These difficulties are solved by a type of annealing technique, which we call the frustration accumulation method (FAM). DSN-FAM works only with local information, and no global functions or global parameters such as a temperature are used. DSN-FAM thus works autonomously. That is, no external control is necessary while operating. Experiments show that this method does not fail to find a solution and the execution time is less than one tenth of Boltzmann Machines. The performance can be easily and almost linearly improved by parallel processing using tens of processors.

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., Unpublished, 1996.

[ 日本語のページ ]
[ Paper PDF file ] [ Paper postscript file ]

[ Several constraint satisfaction problem demos in Java (You can change catalysts, rules, and frustration.) ]

Abstract: A method for solving large-scale constraint satisfaction problems is proposed in the present paper. This method is stochastic (or randomized) and uses local information only, i.e., no global plan is expressed in the program and the computation refer to no global information. This method uses CCM (Chemical Casting Model) as a basis, which is a model for emergent computation proposed by the author. The original CCM-based method minimizes the number of constraint violations not directly but throught optimization of local functions, which are called LODs (local order degrees). This method sometimes falls into a "local maximum." This difficulty is solved by a type of annealing, which we call the frustration accumulation method (FAM). FAM also works only with local information. No global functions is used in FAM, No global parameters such as temperature are used, and global control is thus unnecessary. Experiments show that the performance of this method is not very sensitive to parameter values. This means that parameter tuning is easy. In several problems, the performance is comparable to conventional simulated annealing or GSAT, which are based on global evaluation functions. Because of the nonexistence of global information reference, CCM with FAM can be parallelized very easily. Thus, the performance is improved and is almost linear in certain cases.

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., SIG PPAI, Japan Society for Artificial Intelligence, Feb, 1996, Published by JSAI.

[ 日本語のページ ]
[ Paper PDF file ] [ Paper postscript file ]
[ Paper DVI file (except figures) ] [ Figures in EPSF format : 1, 2, 3, 4, 5, 6, 7, 8 ]

Abstract : Two methods for solving large-scale constraint satisfaction problems using parallel processing are surveyed in the present paper. These methods are based on CCM, which is a model for emergent computation. The number of constraint violations is minimized in these methods. The minimization is performed by optimization of local functions. The computation is stochastic and no global information is used. An annealing method called FAM has been introduced to avoid ``local maxima.'' FAM also works only with local information. Two types of parallel processing of CCM-based constraint satisfaction using FAM has been tested. One is a parallel search and the other is a cooperative search. Our experiments has shown that both methods improve performance almost linearly in large-scale graph coloring problems when the number of processors is ten or so.

Introduction to this research theme: CCM: Chemical-Computation Model

Kanada, Y., 19th International Symposium on Artificial Life and Robotics (AROB 2014), 2014-1.
[ 日本語のページ ]
[ Paper (updated after the symposium) ]
[ Slides ]
[ Printing process (YouTube) ]

Abstract: 3D printing technology usually aims reproducing objects deterministically designed by 3D CAD tools. However, 3D printing can generate patterns similar to randomized (non-deterministic) 1D or 2D cellular automata (CA). Cheap fused deposition modeling (FDM) 3D printers can be used for this purpose. By using an FDM 3D printer, melted plastic filament is extruded by a hot nozzle to shape a 3D object. They can generate CA-like patterns with constant head motion and constant filament extrusion and with unintended fluctuation but no explicit randomness. Because of fluctuation, every time the printer generates a different emergent pattern. This paper proposes a method for printing seaweed-like patterns of 1D and 2D CA using FDM, and computational CA models. This method will open a new horizon of 3D printing applications.

Introduction to this research theme: 3D shape formation technologies

Kanada, Y., 8th International Workshop on Natural Computing (IWNC 2014), 2014-3.
[ 日本語のページ ]
[ Slides ]
[ Book ]
[ Printing process (YouTube) ]

Abstract: Fused deposition modeling (FDM) is a 3D-printing method that shapes 3D objects by layering melted plastic filament. The process of this type of 3D printing can be regarded as asynchronous cellular-automata because it generates 1D on-off pattern per a head motion. Especially, by a constant head-motion at reduced constant extrusion-velocity, a 3D printer can generate self-organized grids or similar structures, which is much finer than artificial (i.e., program-controlled) patterns. Depending on the parameter values, i.e., layer depth, extrusion velocity, and so on, the generated pattern varies among regular stripes, stripes with crossing waves, and splitting and merging patterns. Some of the patterns can be simulated by a computational model, i.e., asynchronous cellular automata.

Introduction to this research theme: 3D shape formation technologies

Kanada, Y., 20th International Workshop on Cellular Automata and Discrete Complex Systems (Automata 2014), July 2014.
[ 日本語のページ ]
[ Paper PDF file ]
[ Paper PDF file (extended ver. for IWNC8 book) ]
[ Slides (reduced size) ]
[ Slides (with a movie, Keynote) ]
[ Printing process (YouTube) ]

Abstract: 3D printers are usually used for printing objects designed by 3D CAD exactly, i.e., deterministically. However, 3D printing process contains stochastic self-organization process that generate emergent patterns. A method for generating fully self-organized patterns using a fused deposition modeling (FDM) 3D printer has been developed. Melted plastic filament is extruded constantly in this method; however, by using this method, various patterns, such as stripes, splitting and/or merging patterns, and meshes can be generated. A cellular-automata-based computational model that can simulate such patterns have also been developed.

Introduction to this research theme: 3D shape formation technologies