"... and no one shall work for money, and no one shall work for fame; But each for the joy of the working, and each, in his separate star, shall draw the thing as he sees it, for the god of things as they are"

-Kipling

 

FPath_Ex005: Stigmergic Fill

Background

FPath is a project to explore the possibilities of the Feynman Path to Nanotechnology. Essentially this means using tools to make small tools which then make smaller tools. See the main FPath Project page for more details.

This experiment demonstrates the 2D filling of a space through the use of stigmergy in a graphical context ("Graphical Stigmergy"). In specific, red sand is pushed onto the area of a virtual green rectangle and the resulting image processing clearly indicates which areas have been filled and which require further processing. The specific algorythm described has been named "Stigmergic Fill".

The Goal

The target goal of this experiment is to:

Demonstrate a 2D space filling algorythm based on a modification of the results of Experiment 004.

FPath Ex_005 Space Filling Example

This experiment is intended to be part of a larger toolkit which will hopefully be useful in future Feynman path experiments. If the path of a tool head can be continuously corrected independently of the quality of the actuators - closed loop control in other words - then a lot of errors can be removed. This is important because as you have machines make smaller machines, the effects of errors compound.

Achieving the Goal

This experiment was entirely software based and no changes were made to the hardware. Changes were made to the Walnut software. The starting point for this experiment is Walnut Server/Client version 00.02.06 and the changes made have been released as version 00.02.07.

Below is a specific list of the steps involved in reaching the goal. All of these steps are discussed in considerably more detail in the video which documents this experiment. Below is a descrption of the adaptations made to the image processing code in the Walnut Software version 00.02.06 to change the virtual green area to black where any red color underlies it.

  1. Implement an in-memory bitmap to provide backing store holding the virtual green area. This is called the "area bitmap"
  2. Implement a second in-memory bitmap to provide an overlay which will be composited onto the image frame. This is called the "overlay bitmap"
  3. For every video frame, copy the area bitmap onto the overlay bitmap. This completely removes any previous changes to the overlay bitmap and provides a fresh start for each video frame.
  4. Raster through the pixels on the image frame and detect the color.
  5. If the color is red then look at the pixel at that location on the overlay bitmap. If that pixel is green change it to the color black.
  6. Once all pixels have been processed, place the overlay on top of the image frame. The viewer will see a normal image with a green area placed upon it. Any areas of the image frame which have red pixels under the virtual green area will appear colored black.
  7. If any green pixels on the image are interpreted as "this area needs red material" it is easy to determine which areas remain to be filled.

The Result

The experiment was successful. Red sand was placed on the experimental bed and manually moved into position. Any areas under the virtual green area instantly turned black. Although the re-arrangement of the red material was manual it would not be hard to code up actuator movement to fill the area using the information on the video frame.

Interestingly, events which disturb the fill, however caused, are immediately evident to any entity performing the fill. Thus there is no need to monitor, internally record events and build a model. With this style of control reality is it's own model.

Algorythmically, indirect coordination via the modification of the environment is called stigmergy. As discussed in Experiment 004, the general name for this technique is "Graphical Stigmergy". I think I will refer to this particular algorithmic variation as "Stigmergic Fill".

Video of a virtual green area being filled with red sand and changing color to indicate the filled areas.

This experiment was also discussed in a post on the RepRap Blog: Stigmergic Fill

This experiment is now complete. The Walnut software associated with this experiment can be found under Commit ID: 1fb9950 on the GitHub repo.

Future Use

The implementation of Stigmergic Fill capabilities in the Walnut software will probably be a valuable part of the tool kit used to move further down the Feynman Path and create smaller machines from larger ones. The idea is that a virtual area can be filled and that reality is continually used as the definitive model for determining further actions. The error correcting, closed loop feedback, nature of the Walnut software should help remove cumulative errors.

License

The intellectual property rights to all new and/or original ideas and technologies documented under the FPath project and sub-projects are claimed in full by the author and are immediately released into the public domain under the terms of the MIT License. Any ideas, techniques, processes or methods of work documented in the FPath project and sub-projects must be considered to be prior art and must be cited in any patent applications.

The contents of the FPath project and sub-projects are provided "as is" without any warranty of any kind and without any claim to accuracy. Please be aware that the information provided may be out-of-date, incomplete, erroneous or simply unsuitable for your purposes. Any use you make of the information is entirely at your discretion and any consequences of that use are entirely your responsibility.