This repository has been archived by the owner. It is now read-only.
README Kilobot App - A Kilobot simulator and swarm pattern designer Copyright (C) 2012 Antti Halme / ICS / Aalto University 0. REQUIREMENTS 1. OVERVIEW 2. USAGE 3. APP DESIGN 4. PROGRAMMING MODEL 5. REFERENCES 6. TODO/WISHLIST 7. LICENSING 0. REQUIREMENTS * Reasonably new Python, developed on Python 2.7.3 * The pygame library, developed on pygame 1.9.1 (see ) * the pygame utility library for GUI (included as local library) Developed on Ubuntu Linux, following should set you up fine $> sudo apt-get install python python-pygame * The latest and greatest version of this can be found from Github $> git clone https://github.com/ajhalme/kbsim.git 1. OVERVIEW Kilobot App features a Kilobot simulator (KBSimulation) and a simple collective pattern designer (KBDesigner). KBSimulation is a simple simulation environment, so far mainly used in prototyping control software ideas and collective algorithms on a swarm of Kilobots [1, 2, 3]. Kilobots are constrained yet capable little robots, with a somewhat low unit retail cost (à ~100€). KBDesigner is an alpha stage tool for designing collective patterns for Kilobot swarms. The designer produces a pattern specification, used by a Kilobot swarm as a set of instructions for rendering somewhat arbitrary visual patterns. At this time, the "bot rendering" feature is very limited, as the necessary control algorithms for arbitrary form generation are very limited. The application is written in Python using the SDL-derived Pygame library  and features dynamic robot instruction loading, a primitive user interface and of course a feature level model of Kilobots and their interaction. The simulator is modular to a degree and could be made to support other bots relatively easily. Kilobots feature a multicolor LEDs, neighbor-to-neighbor distance sensing (NOTE: no bearing!), a rechargeable battery, two vibration motors that enable slapstick movement either clockwise, counterclockwise or approximately forward. Kilobots communicate in a very primitive way: they can send and receive IR pulses, relying on a reflective surface to enable message broadcasts of 23 bits at a range of up to 10cm. 2. USAGE The Kilobot application runs modules (KBSimulator, KBDesigner) and overlays a simple GUI (KBDialog, KBControl, KBGUI) on top of the executing module. A configuration data structure is passed around in the application and is based on the configuration file (e.g. default.cfg) and possible command line parameters that override the file. The application configuration allows the manipulation of relevant variables ranging from color schemes to radio ranges and bot behavior. The key parameters: * the number of bots to populate the world with (2-100 or even more, if HW willing) * the behavior/program to load in the bots (currently only one is supported, could easily support multiple different) * the initial formation in which the bots lie * possibly a seed value for the random function (identical simulator runs) A helper script './launch' assists in executing the application, supporting a range of optional parameters. The powerful parser libraries (argparse, ConfigParser), munch the configurations and support a variety of calling schemes that guide the launch process, e.g.: $> ./launch -h $> ./launch --help $> ./launch -n 10 -p Bots/Listenbot.py -f RANDOM $> ./launch -c experimental.cfg -p Bots/Coolbot.py -f RANDOM $> ./launch -c experimental.cfg -p Bots/Coolbot.py -s 42 $> ./launch -p Bots/Franklinbot.py -f CIRCLE -n 8 $> ./launch --dialog $> ./launch --designer -n 9 The simulator (and the designer, too, when applicable) support on-the-fly interaction by the following keys: a - abstract mode toggle (faultless RX/TX, connection graph, pseudo-reduction to points) c - draw links d - draw debug information g - draw grid h - show formation information (disconnected) i - draw bot info (e.g. secretID) k,l - FPS up/down (use slider instead) n,m - interference noise multiplier up/down (the UI panel shows the percentage of OK msgs of all send attempts) p - print (disconnected) r - draw radio range s - simulation stop/pause t - draw traffic (RX and TX for each node) u - draw user interface panel (fps, round number, etc) ,,. - ambient noise up/down PGDN/PGUP - 90 degree world rotation CW/CCW ESC - end simulation Mouse is also of use: mouse L - make a connection between bots (designer mode, disconnected) mouse R - move bot around The simulator also has overlay UI items: * toggle for fullscreen * designer-button to launch the designer * restart to re-launch the current execution (with the previous config) * FPS slider to set the target speed of the simulation * printouts: round, fps, noise info The designer also has overlay UI items: * toggle for fullscreen * clear connections between bots * connect the bots in the design by magic * launch a connected design to be rendered in a simulation Again, the designer (and the rest, too) is very much under construction. 3. APP DESIGN The Kilobot App features a simulator and designer tool. To accommodate both at the same time, a module system was implemented for the application base: both KBSimulation and KBDesigner are launched as needed. The modules share a configuration state, mostly derived from a configuration file, but overridden by command line arguments to the launcher script. The configuration object is also used to carry the designer output to the rendering simulation. The KBSimulator is essentially an update-draw loop with bot-specific function pointers so that at every time step, all bots run one atomic function. This suggest a state machine based programming model, described in the next section. The KBDesigner is a barebones GUI in the spirit of the simulation environment. It features a simple connection algorithm, useful for building a connected graph out of the robots. Connectedness is one of the (implicit) requirements for launching a rendering simulation. As the rendering algorithm is very simple, for any pattern formation to succeed, careful manual tuning of the formation rules is almost certainly needed. In the folder Bots/, we have the programs themselves, modules written in Python containing the program to be run on each bot. For now, and in the spirit of swarm computing, all bots run the same program. The bots have a backward link to the simulator, allowing for more complicated things, such as overriding the debug print function or using the uniquely identifying secretID-parameter to set nodes to run different version of a program (e.g. leader and followers). In the folder libs/, we have the vector type libary Vec2d  and the (possibly discontinued) pygame utilities library , used for th GUI. The *.cfg-files, notably default.cfg, are the main configuration mechanism, outside command line parameters. They should be relatively self-explanatory or at least easy to play with. The whole configuration scheme relies on the excellent Python Standard Library utilities ConfigParser  and argparse . ./launch is the main script of the application, used to launch the Kilobot App. The main function is very simple: 1. parse config file and overwrite config values for those given as arguments 2. build a new KBApp instance with that configuration 3. run KBApp.py holds the highest level of abstraction, launching modules as specified by the configuration object (a map) until shut down by the user. KBControl.py holds the GUI elements to be overlaid on their respective modules. They derive from pgu-elements, the design of which is heavily influenced by the HTML object model and layout concepts. Both include callback functions that interact with the module by using form-based message passing. KBDesigner.py holds the massive work-in-progress designer module. The main loop is in the run() function, maintaining the GUI and updating the design. The basic functionality is built out of the following: * the analyzer - all nodes are properly linked to their predecessors * the connector - kNN backwards assignment * the executor - launches the simulation based on the (connected) design KBDialog.py is a sketchy GUI piece, a graphical layer for the command line parameters for both the simulation and the designer. KBGUI.py does the heavy lifting for user interaction. It maintains the draw surface (e.g. keeps the nodes in sight), handles UI events by calling appropriate processing functions and defines and manages the visual appearance of all graphical elements both in simulation and the designer tool. KBSimulation.py defines the simulator functionality, including formation control, bot instantiation, collision detection, messaging control, the stepwise robot execution and other things. Like the designer, it has a main loop in the run()-function, where everything is updated and drawn and processed. Kilobot.py defines the robot functionality and contains a library of common simulation idioms. The idioms are short functions, to be included in the function list that represents the program, the algorithm. These include functions that simulate the Kilobot C API (e.g. message_out) as well as useful little things (e.g. reset_rx) and entire features (e.g. the history routines). Some of the functions are considered internal, some to be used as parts of algorithms to be implemented. LICENSE holds the GPLv3 and README is what you're reading. LICENSE README lib/ Bots/ .---------. .---------. ./launch ----> | KBApp | < | Kilobot | '---------' '---------' // \\ .----------------. .--------------. | KBSimulation | | KBDesigner | '----------------' '--------------' \ / .---------. | KBGui | '---------' / \ .-------------. .------------. | KBControl | | KBDialog | '-------------' '------------' 4. PROGRAMMING MODEL Bots are created by writing a new Python module in which there is a class that inherits the Kilobot class and replaces its self.program field with a function pointer array. Additionally, for import semantics to stay reasonable, a load() function is to be implemented in the new module, called at simulation startup. Single functions in the robots can be as elaborate as needed and can use all tricks possible in Python. To keep in mind is the fact that from the simulator's perspective, the whole function is atomic and is run in a single step. This means that, e.g., delay or real durations in execution are irrelevant, affecting only changes in the apparent FPS of the simulator. In short, this suggests a finite state machine -based program design. A program counter, self.PC, tracks the program execution, operating as a pointer to the function pointer list. The counter enables (clunky) looping and programmed control flow modifications, even self-modifying code. With that, the whole model can be thought of as high-level programming with low-level ideas. The parent class Kilobot.py features a set of basic functions that can be called directly as a single time step, e.g., self.program = [..., self.toggle_tx, # note: self.toggle_tx , NOT self.toggle_tx() ...], or included in a function and called through that: self.program = [..., self.myfunc, ...] def myfunc(self): self.toggle_tx() The Kilobot default library contains a bunch of value fields, some simulator specific tricks, a simulated C API in the spirit of the real C API (to make the eventual porting to C possibly easier) and more advanced constructs, such as the message history API. Simple examples to get a grasp of the programming model include * Bots/Defaultbot.py, here in it's entirety: from Kilobot import * def load(sim): return Defaultbot(sim) class Defaultbot(Kilobot): def __init__(self, sim): Kilobot.__init__(self, sim) self.program = [self.loop0] * Bots/Blinkybot.py * Bots/Radiobot.py Some of the more complex examples include: * Bots/Franklinbot.py * Bots/Wavebot.py * Bots/Abot.py 5. REFERENCES  K-Team. Introduction to Kilobot. http://www.k-team.com/mobile-robotics-products/kilobot/introduction  Kilobot: A Low Cost Scalable Robot System for Collective Behaviors Michael Rubenstein, Nicholas Hoff, Radhika Nagpal, Technical Report TR-06-11, Harvard University ftp://ftp.deas.harvard.edu/techreports/tr-06-11.pdf  Kilobot project homepage. http://www.eecs.harvard.edu/ssr/projects/progSA/kilobot.html  About Pygame. http://www.pygame.org/wiki/about  http://www.pygame.org/wiki/2DVectorClass http://karpathy.ca/phyces/tutorial1.php - Phyces  http://www.pygame.org/project/108/ http://code.google.com/p/pgu/ - Phil Hassey  http://docs.python.org/library/configparser.html  http://docs.python.org/library/argparse.html 6. TODO/WISHLIST - better module abstraction and general design, aim for MVC * have KBSimulation and KBDesigner derive from a KBModule - cleanup the UI, remove redundancies from keys - maintain fullscreen when switching modules - comments, documentation * app design - smarter designer * "connect" does not reset, builds on existing linkage * a "check" or "analyze" feature * smoother "connect" algorithm, simplify implementation * derive KBDesignerGUI from KBGUI (also KBSimulationGUI) - rethink radio stuff, particularly noise - use (pygame)-events more in the simulator - draw smarter, more speed from better-than-trivial algorithms - non-Renderbot rendering of given form somewhere - target form shadow in render simulation - signnificantly better Renderbot(/Abot/LineBOT/...) control scheme - more algorithm prototypes - fix non-termination heisenbug from Wavebot - add error to differential drive, add imprecision in motion - pay attention to specification compliance - the better-than-expected transmission range hasn't been considered in either the algorithms or the simulator - complete redesign/rewrite with proper parallel/concurrent execution 7. LICENSING Kilobot App - A Kilobot simulator and swarm pattern designer Copyright (C) 2012 Antti Halme / ICS / Aalto University This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>.