Ryanne Dolan

self-organizing ABP networks

2007-10-05T08:13:00.000-07:00

The fact that ABPs can learn patterns with very little information or feedback means that the ABP can be used as a computational "Lego brick" with which to build pattern recognizers and classifiers. Since each ABP can learn independently, learning in groups can only increase their computational power. However, this requires ABPs to communicate in order to prevent redundancies. In other words, N+1 ABPs is better than N only when the +1 ABP is different somehow from the other N.

At the same time, the information communicated between self-organizing neurons must be kept at a minimum in order to set them apart from global learning algorithms like the BPN. While global information means neural networks can learn much faster (in theory), self-organizing neural networks are trying to fit a different niche. A familiar example is found in Particle Swarm Optimization, which can utilize either global or local (or both) communication between particles. Global communication means much faster convergence, but "localized learning" means that the algorithm can be easily distributed and parallelized.

Once we have a network of ABPs that learns better than a single ABP, without sharing global information, we've found a self-organizing neural network that is simple enough to implement in hardware.

adaptive bias perceptron (ABP)

2007-10-04T23:06:00.000-07:00

I've developed a new artificial neuron based on the oldest neuron around: the perceptron. My simple modifications make the Adaptive Bias Perceptron an extremely fast and accurate learner. The ABP can be used in both supervised and unsupervised training scenarios, and is simple enough to implement in hardware.

My primary goal when designing this neuron was to develop a processing element that could learn patterns and classifications with as little input or feedback as possible. My secondary goal was to find a neuron which could self-organize with neighboring neurons with a minimal transfer of information.

My solution uses the same activation function as the perceptron:

y = W*X - b

The name ABP comes from the fact that the bias 'b' is learned separately (though not independently) from the weights 'W'. Each time the neuron fires, the bias is updated according to a linear differential equation:

b' = c*(y-b)

where 'c' is a small learning coefficient. This has the affect that 'b' approaches the expected value of 'y'.

While learning the bias, the weight vector 'W' is updated according to the following bizarre learning function:

W' = g*(b-y)*X

where 'g' is a large learning coefficient.

The neuron is trainable in both supervised and unsupervised scenarios. Apply the learning function continuously, and the neuron will find a boundary dividing the input space into somewhat symmetrical halves. Or, apply the learning function only when an error is made, and the neuron very quickly converges on a solution and stops learning.

In most cases, the ABP can be trained to classify linearly separable data with only a few sample vectors.

acedemic research

2007-10-04T22:29:00.001-07:00

So I'm in grad school now, pursuing my PhD in computer science. I joined the Vision Guided and Intelligent Robotics (ViGIR) lab under Dr. DeSouza, and am researching self-organizing systems.

I've entered two campus poster competitions to exhibit my research, which from now on I'll be chronicling here.

My latest research is on self-organizing neural networks. In computer science terminology, my research is closer related to swarm intelligence than neural networks, but anyone outside my field would call my work a study in artificial self-organization.

In this context, self-organization refers to the complex, emergent behavior of systems composed of many agents with limited, localized communication. Termites, schools of fish, and slime molds are common biological examples of such systems. In the brain, neurons are the ideal self-organizing components, with relatively simple local interactions but all the powers of the human brain when carefully structured.

My current project involves two major landmarks: the development of a neuron capable of unsupervised learning, and the structuring of these neurons into self-organizing networks.

new project: agent-based programming framework

2007-06-20T09:40:00.000-07:00

I've started a new project which aims to simplify robotics software development. As usual it is open source under the MIT public license and hosted on code.google.com.

Read about it here.

ping-search implemented

2007-06-01T22:43:00.001-07:00

I've implemented a simple ping-search prototype for the UMR robots. I'll be testing it tomorrow.

The algorithm I've implemented is extremely simple; there is definitely much room for optimizations and improvements. It works like this:

The algorithm ignores accelerations altogether, under the assumption that the robot can change velocities rather quickly, and there is never any reason for it to slow down or speed up gradually. The algorithm searches for the best "trajectory" which comprises an angular velocity and forward velocity.

Favoring the full-speed-ahead trajectory, the search starts with the robot's current angular velocity and full forward velocity. To target a waypoint, the initial angular velocity is skewed towards the target. This initial trajectory is then projected through time for a given number of seconds. If the trajectory is sufficiently low-cost over this time period, the search stops and robot goes full speed ahead at its existing angular velocity.

If the trajectory cost is too high, it is thrown out and a new angular velocity is attempted. The new angular velocity is chosen based on how good the old one was. If the trajectory was nearly passable, then the angular velocity is changed only slightly.

This process is repeated for a small number of angular velocities. Each new angular velocity "guess" is made based on the cost of the previous guesses, in a gradient descent sort of search. If a good trajectory is found this way, the robot's control system is adjusted appropriately and it moves full speed while turning through an arc.

If after a small number of angular velocities no good trajectory is found, the algorithm will try another handful of angular velocities, but at a slightly lower forward velocity. This process repeats for a small number of forward velocities, until the search gives up and returns a trajectory with forward velocity zero.

The robot, therefore, will tend to go full speed ahead, and gradually arc around obstacles as they appear in the model. If there are few obstacles around, the search is very quick, as the first couple of trajectories should work. If no clear path lies ahead, the robot will stop after trying a bunch of trajectories.

It is conceivable to fall back on our existing guidance system in the case where no path can be found. Also, as usual the robot can try backing up when it gets stuck. While the search isn't very intelligent, it can model the robot's actual trajectory rather well and insures that any path the robot takes is safe (though not necessarily the best).

ping-search algorithm

2007-04-29T18:42:00.000-07:00

I have been trying to think of a light-weight obstacle avoidance algorithm for small UGVs and UAVs. The UMR Robotics Team uses A*-search for our ground vehicles (and so does pretty much everyone else) but this algorithm doesn't scale well to high speeds, long distances, and three dimensions of travel, all of which a UAV would require. My proposed algorithm is highly scalable; everything from a cluster to an 8051 could run it with no problems, and more processing power means higher speeds of travel are possible.

I call it ping-search. The basic story describing the algorithm is as follows:

You are in a pitch-black maze with an infinite supply of ping pong balls and a demon chasing you. You want to run as fast as possible through the maze without running into walls. You imagine how bats fly in the dark, and start throwing ping pong balls in front of you to hear if a wall is there.

After a frantic minute of running and throwing balls, you devise a strategy to maximize your speed through the maze. You throw a ball straight in front of you and listen for a bounce. If it takes a long time or you never hear it at all, you know there is nothing in front of you for a good distance, so you run as fast as possible in the direction of the thrown ball. If instead you hear a bounce close in front of you, you slow down and throw balls slightly to the left and right of where you think the first one hit. If the balls on the left/right take longer to bounce, you turn left/right a bit and keep throwing. You adjust your speed based on how long it takes for there to be a bounce. Also, you throw farther to the left or right as you get closer to a perceived wall.

Then, you realize that you can throw balls with spin so they curve left or right. Now the trajectory of the balls matches more closely your own trajectory. So, instead of changing the angle of a thrown ball, you change its angular velocity. Instead of taking sharp turns after hearing a bounce, you make gradual turns based on the angular velocity of the longest-lived ball.

Now you run quickly through the maze throwing straight or curving balls and further optimize the process by pipelining things a bit. Instead of waiting to hear a bounce, you throw multiple balls in rapid succession and echo-locate the point of impact. Depending on how fast you can throw balls, you may have several balls in the air at once this way. You begin to feel like a bat flying through a cave, when the demon catches up to you (he can see in the dark) and eats you. Oh well.

stout progress

2007-03-12T23:32:00.000-07:00

Currently Stout includes a parser, an abstract syntax tree, and an abstract semantic graph.

The parser is an LL(1) recursive-descent parser for a very simple object language. The language is not meant to be a programming language; it is provided as a target for translators.

The parser builds a big AST in one pass as it traverses the input stream. The AST stays persistent after the stream closes and can be used to construct multiple ASGs from a single parser instance.

The parser provides a "close" method which constructs an ASG from the AST. The ASG is equivalent to a closure object which is evaluated as it is constructed and destructed. The ASG is composed only of objects, basic operations, and other closures. All blocks, functions, loops, etc are implemented as closures, which are executed simultaneously and block until dependencies are resolved.

Thus, every major mechanism and data structure I can think of is done. Now I just need to make the language and ASG Turing complete, and I'll have a working pipelining runtime.

sar-os for mobile devices

2007-01-22T14:37:00.000-08:00

With all the hype surrounding cell phones recently (thanks largely to the iPhone) I've been thinking more about mobile devices than I have since my PocketPC jaunts in high school. As I noted earlier, I spawned the stout project after realizing that the sar-os virtual machine was growing far too complicated to fit with the spirit of the "Small ARchitecture Operating System". Now that an auto-parallelizing virtual machine is not on the list of priorities for the sar-os project, I can safely revert to using Lua as the native shell language. This significantly reduces my work load for the project and means I can focus more on the kernel.

So now sar-os will likely turn out to be a small, highly portable operating system which will be nearly ideal for mobile devices such as cell phones and PDAs. In addition, I of course plan to stick with the original motivation of the project and make sar-os easily deployable, so that a developer can run sar-os on top of existing operating systems.

That last benefit works doubly well for the mobile device market, since developers using sar-os will be able to run the same programs on multiple platforms, including their cell phone and desktop computer.

stout design

2007-01-22T14:06:00.000-08:00

For stout I've decided to make the virtual machine evaluate an execution tree rather than bytecode. I believe the scripting language Ruby does this. There are several advantages to using an execution tree, including:

- multiple threads can execute concurrently on different branches of the tree
- the compilation step is simplified, in that the parser's recursive decent tree is isomorphic with the execution tree
- import functions (ie Lua's 'require') can add to the execution tree at runtime
- the interpreter can simplify the execution tree on the fly to improve efficiency

The obvious disadvantages are that the implementation will likely be a lot slower (compare Ruby to Lua) and that there is no easy way to spool compiled chunks to disk. The latter is a bit worrisome for me, because I want stout to be able to download and execute code from remote machines. A compiled format would be more compact and therefore reduce download time. However, remember stout will interpret only a very low-level language, which will at least be more compact than say a C++ source file (it will be more like an assembly file).

NxPg alpha

2007-01-18T07:56:00.000-08:00

I've finished the NxPg engine and have posted a test site on our company website:

rollaeng.com

We will add a control panel so that users can add and remove pages, upload content and such. We'll also augment the edit interface with buttons and wizards to make adding NxPg "objects" easier.

stout on google

2006-12-13T20:02:00.000-08:00

I've created a project on Google Hosting for stout. Google probably hates me by now.

code.google.com/p/stout

One of my biggest complaints with C++ is that I always seem to spend more time organizing classes than actually writing functional code. However, I think most of the object orientation for this project is already finished, and now I just have to go through and implement the many functions I've left undefined.

The stout VM will implement a lot of functionality that I usually consider to be the job of a compiler or translator. For example, the VM performs scope resolution, keeps track of variable names and types, and natively supports vectors, matrices, tables, etc. This means that writing a scripting language translator for the stout VM will be fairly trivial. Basically, a dumb yacc parser that generates stout assembly will suffice.

I will undoubtedly write several toy languages for stout, and will at the very least write a Lua translator for it.

stout vm

2006-12-11T10:21:00.000-08:00

Maybe I will name my newest VM after a beer.

Stout so far supports all primitive C types; I'm working on references (pointers), arrays (vectors), tables (maps), and matrices.

I'm experimenting with novel ways of organizing the VM. I've never implemented a VM in C++, and it is definitely proving to be quite a bit different. I'm really pushing the limits of C++ with this project already.

Stout is designed to take advantage of the C++ runtime whenever possible. For example, it relies on polymorphism to determine which instruction to apply to a register based on the register's type. Other VMs (like sar-vm and Lua) accomplish this with union/struct tricks, but with C++ there is of course no reason to re-implement polymorphism.

Also, instead of loading and executing bytecode, I would like to try loading a list of member function pointers which I can call one at a time. This way, the C++ runtime takes care of just about everything.

The effect of all this is highly elegant code which probably won't run quite as quickly as say Lua or Java; however, it should be so simple to interface the VM with existing C++ that I don't think anyone will care if it is a bit slow.

parallel vm

2006-12-07T19:59:00.000-08:00

While writing my virtual machine for sar-os, I've conceived some interesting algorithms for an auto-parallelizing interpreted language. Under sar-os, the VM is responsible for load-balancing, scheduling, etc because the sar-os kernel does not implement multiprogramming. This is because handling multiple processes and threads efficiently requires getting intimate with the processor and hardware, while one of the goals of sar-os is to be entirely platform independent (quite a lofty goal for an OS).

At the moment, the sar-os kernel is largely finished, but until the VM is working the entire OS is mostly useless (except maybe as a DOS replacement).

The sar-os VM schedules and load-balances on the fly, but parallelizes and distributes bytecode at compile-time. This means that the system must re-compile all programs each time a new node is added to the cluster. This is acceptable in my opinion, because in most situations processors don't just drop off the radar randomly, and if they did at least a reboot would be necessary anyway.

The inherent flaw with the sar-os paradigm that has been haunting me since its inception is that without hardware-specific code, it is impossible to take advantage of multiprocessor and multi-core systems. Since multi-core processors (especially) seem to be the next great fad in computing power, this lack of support promises to be a huge problem for sar-os that won't go away without major patches to the kernel.

This doesn't mean that sar-os will forever be useless. At least it will run well on large clusters of junk computers. But for HPC applications, I think another solution is in order.

I plan to spawn a new project which will implement a auto-parallelizing, cross-platform virtual machine. It will be similar to Java in a lot of ways, though will take full use of multi-core and multiprocessor systems. When coupled with something like OpenMosix, the VM will be a viable target for large-scale cluster HPC applications.

I'll likely write the VM in C++ and borrow the basic bytecode interpreter from sar-os. As always, I need to think of a name for this project before I start writing too much code. More to follow.

nxpg born

2006-12-07T17:57:00.000-08:00

My company, Rolla Engineered Solutions, LLC, is awaiting approval for our biggest contract yet. We will be designing and hosting two websites for a startup magazine company and publisher. Our clients want to be able to edit content, upload pdfs, and make general changes to the site without experience in html. Of course, a wiki or CMS comes to mind immediately, but most such systems produce slow and unprofessional pages (in my opinion, at least).

Our proposed solution is to develop a new wiki system which we call nxpg (pronounced "next page"). The nxpg engine will generate two parallel websites: one for public users and one for internal users. This means that the website as viewed by the world is always as professional, fast, and un-wiki-ish as any other site, but the internal site allows wiki-like online wysiwyg editing.

Unlike other wiki systems, nxpg doesn't use a restrictive template format. Any html document can be used as a template by replacing the document's textual content with content placeholders. The placeholders are replaced dynamically with real content when the page is accessed online.

This means that we can design custom templates with existing web publishing tools, and produce truly unique websites for our commercial customers.

nxpg is released under the MIT license and owned by Rolla Engineered Solutions, LLC. You can find the source code here: code.google.com/p/nxpg