Monday, July 04, 2011

Digital Video Broadcasting... how it works...

I'm reading up on Digital Video Broadcasting standards. The DVB standard is for receiving digital video back in your home. There are a couple of subtypes in this main category which distinct themselves by their error correcting facilities (based on what's needed over the medium that they are transmitted), bandwidth, etc. The DVB-S standard is one of the things I'm most interested in. Digital Video Broadcasting is usually done with MPEG-2 transport streams. Suppose you have a video on your computer and a bit of music, along with some information on what else is available on your channel. The transport stream is composed by multiplexing all the information together (rather fast) and creating one larger bitstream that can be transported using either DVB-T (terrestrial), DVB-S (satellite) or DVB-C (cable).

I had thought that analog TV would be more resilient to noise created in the atmosphere, but this is not necessarily the case. If you send a file over the ether composed of 0's and 1's, then any noise or interference in the stream may cause a bit to be misread or misinterpreted or missed. Since the playback of a file is usually dependent on all the bits being read correctly, this is where you may get huge problems already. One or slightly more bits falling over may already cause the entire stream unusable.

Unless.... you add error correction. But this increases the size of the entire stream... How then...? Well, the MPEG-TS doesn't carry nearly as much information as an analog video stream, because analog stuff is not compressed, although in the analog world you can remove some information without significantly reducing the quality of your experience (one example here is mp3). In analog video, this means you can easily reduce a bit of the color in an image, although luminance (that which you'd see as black and white) is far more important for a person's perception of an image.

Back to MPEG-2 however... digital compression standards rely on encoding those things that matter only once, where 'motion' in the video would typically require you to encode a bit more about some spatial event for example. So a green screen that doesn't change a pixel will be very easy to transmit and extremely cheap, whereas a fast-paced action movie may temporarily reduce in quality a bit, because all the parts on screen are in motion all the time.

Let's assume that we have some digitally encoded video+audio and that it is ready for transmission. For transmission in DVB-S and all the error correction abilities we need to have at the receiver side, the huge file is packetized into 187 bytes and then a sync byte attached to the start of this "packet". The interesting thing here is that this file may be rather regular in terms of how one byte and its neighbor relate to one another. One interesting finding is that equal bytes that follow up one another may cause more reception problems at the rx side than a noisy transmission will be, because there's more variation.

For this reason, each byte in the packet, excluding the sync byte, is 'AND-ed' with a pseudo random number generator (a simple one that is). This means that some bits now turn on, others turn off and this machine has a certain period over which it operates. This PRNG is reset after every 8 frames of transmission.

What we're getting now is already an interesting stream of information that's nicely packeted, more resistant to some errors. Each packet is fed through a "Reed Solomon" encoder. This is an error-correcting encoder that has the ability to correct 8 bytes of information from this packet at the rx side. So this is the first stage where we're adding additional information to the stream that is going to help us later on. Reed-Solomon (RS) is also used frequently in other mechanisms, like storage, data transfer for other applications (CD? HD? etc.). Sometimes it's getting replaced by other algorithms like Turbocoder (space missions, etc.) and so on. Just think... the images you're seeing from Space sent by those satellites also use these schemes to ensure no bits get inverted/changed during this transfer.

The next step after the RS is some interleaving. Interleaving is a process where you shuffle parts of one packet with parts of another packet. The reason for doing this is that errors typically occur in bursts, not like 'hit and run' errors. By shuffling the original position of bytes in one packet with another, the deinterleaver relocates the parts to their original position later. If any error burst occurred, the spread of the damage caused by the error burst is much lower (it didn't zero out 3 bytes in a row, but perhaps one). Thus, it makes the signal again more robust against interference and errors.

After the interleaving, another forward error correction scheme is used called "Viterbi encoding". This may in worst case duplicate the number of bits in the transmissions stream. More bits mean higher bandwidth. The challenge is to fit the entire MPEG-2 stream within around 6MHz of RF bandwidth, so both the original MPEG-2 stream bitrate as well as what happens after that is very important. If Viterbi encoding can be less aggressive, slightly more MPEG-2 data can be sent in the channel before it uses all the allocated (planned) bandwidth.

The steps after this are 'baseband shaping' and 'I/Q modulation'. This means that the digital signal is mapped to an analog signal for transmission. Words you'll see here are "constellation". The kind used in DVB-S is quadrature phase shift keying. This means that a sequence of 2 bits is taken together and mapped to some vector 45 degrees in a constellation space. Being this far apart prevents any errors that may occur and you'd typically choose that based on the amount of expected noise in the channel. DVB-C, the cable kind, has so little expected noise that it uses 64 positions in this constellation instead. This means that in theory, it has 16 times more bandwidth.

Different analog video signals occupy 5-8 MHz in bandwidth. Expressed in Mbits/sec, PAL video equates to 216 Mbits/sec, whereas MPEG-2 compressed PAL reduces that to 2.5-6 Mbit/sec. High value means bitrate when there's lots of motion, the other when there's little. Compressed HDTV is higher than that in the order of 12-20 Mbits/sec. However, this is measured against MPEG-2. H.264 encoding is three times more efficient, so this gets HD video back into reach for actual transmissions. The alternative would be to use different modulation techniques or to occupy a larger portion than 6 MHz in the transmission region.

Some issues still arise... DVB-S was specifically created for LOS conditions away from reflective buildings and other interference sources. As soon as DVB-S is used for terrestrial transmissions this may have a huge impact on video quality. Tests so far indicate this is not necessarily the case and I reckon that with the circular polarized antennas that for example FPV fliers are using for their analog video, the multipathing issues that threaten DVB-S may well be reduced to a minimum.

Tuesday, June 28, 2011

Quad tuning

I made a post to the diydrones website some days ago, explaining some modifications I made to the Arducopter source code. A colleague of mine explained me a couple of things about issues related to aircraft control. The standard Arducopter code has the attitude controller in place and the GPS Hold. I added the velocity controller. As you can see from the diagram, this means that the GPS Hold controller immediately changes the attitude of the quad on the basis of some difference in position. The attitude controller itself just maintains a certain angle setting.

The attitude of the quad may induce a certain acceleration into some direction. When you steer a quad to some location by hand, you don't maintain the angle until you get there, but steer towards the other direction for a brief moment to zero the velocity with the intention to have zero velocity on the intended position.

My experiences with the GPS Hold code in the arducopter are poor. Others have had more success, but I could never find the right settings that made the quad behave correctly in all circumstances.

Because the GPS Hold controller controls the angles directly, but doesn't look at the velocity, it will only zero the velocity after it has passed through the setpoint. This means that with some larger drifts around a setpoint, overshoot cannot be avoided. Aggressive settings then cause overshoot into one direction; the quad then slows down, reverses direction and overshoots the other direction. Thus it oscillates around a position. Higher D-gains help in this regard, but I couldn't get this to calibrate correctly. The I-term does more evil than good and should be used very sparingly.

With the velocity controller in the middle I had more success. The velocity controller is also a better means to control where one is going. Letting go of the sticks means that the quad already attempts to hover around doing nothing. With little wind you'll see that this leads to a near-perfect GPS Hold operation. The GPS Hold code that you do put in than only removes the little offset that does take place due to small disturbances and other inaccuracies due to some dampening filter on the GPS course/speed readings.

In order to calibrate things correctly, start with the last controller going backwards. The attitude of the quad must be maintained with near perfection. Indoors in a large enough area, it should not travel significantly in any direction. If the quad does that, it may indicate:
  • most likely cause: too many vibrations in the quad causing the IMU to get slightly confused at times or over time. It may then tilt somewhat into any direction causing speed to build up.
  • motors not pointing straight up, so that propellers have thrust in the xy-plane.
  • Incorrect response of ESC / motor due to incorrect ESC calibration, defect motor, etc.
I cannot stress enough how important it is to remove vibrations as best as you can, because you get much better results that way. In my case, I've flown with the quad in a situation where it was moving about quite a bit in outdoor environments and making a sound like a lawn mower (you know, where the mower blades cut reeds, those kinds of 'graty' sounds). I found out eventually that my bolts appeared to be tightened, but with a proper spanner could still tighten it further by 1/4 turn. This improvement for about 5 bolts resolved the graty sounds entirely and on the next launch, it hummed perfectly. That is how much bolts / nuts may impact stability, the way how motors are balanced and in turn impact the vibrations on the IMU. So make sure that works ok.

To calibrate the attitude controller, set the tx into attitude control mode of course. Then zero I and D and start with the P setting. You're looking for a P-setting that is just high enough to cause the quad to just about oscillate. Then lower the P setting a little notch (this is a relative operation) and work on the I and D terms next. The I-gain has two purposes:
  • Increase the speed at which you find your setpoint.
  • Resolve any bias that may accumulate in your system.
The bias for example is wind. If your quad already remains very level, in outdoor environments a level quad will drift away slowly on the wind. Suppose that you're activating the GPS Hold controller. Without the I-gain, you'll drift downwind until proportionally speaking, your quad has such an angle that it finds an equilibrium with the wind conditions. The I-gain will start to kick in, increase the angle and the idea is that the build-up of the I-gain over time and the decrease of the P-gain eventually establish a new equilibrium on the exact setpoint. That would be perfect.

The D-gain is there to reduce the speed of approximation towards some setpoint, such that it reduces overshoot of the setpoint (similar to how the GPS Hold working on angles should work).

For the attitude controller, I'm using some suggested values that are not special at all: P=3.4, I=0.015, D=1.2. These are the values for my quad and mine is custom built with relatively large distances between props. It's likely that if you have a smaller quad, you can sustain some more aggressive values.

Soon as the attitude controller is stable, work on the velocity controller. This only has two variables to adjust: P and I. At some point, especially with systems that have low frequency of reads, there's no point to use D-terms anymore. The P-gain for the velocity controller should not be too high to prevent instability. The velocity controller depends on the GPS information and this is basically some complicated piece of hardware nowadays with its own filters, dampeners and other algorithms. It's likely that a high frequency GPS (10Hz) together with doppler shift readings for speed give the best results. I set the P-gain to 0.04, which equates to a 4 degree angle when speed is 1 meter per second. If this is set more aggressive, it's possible that you see a circling motion occur due to the way how ground course is calculated in some GPS's. The I-term is basically determined on the basis of how much 'angle' one would need to compensate for windy conditions (in order to still develop a certain velocity).

Since the velocity controller is already very effective in keeping the quad fixed in place, the GPS Hold controller is just there to resolve any difference in position that still does occur over times in the 20-30 second area. It slowly develops a certain velocity that the quad should have towards the setpoint and slowly retargets the quad towards a certain position. My GPS hold controller only uses a P-setting. An I-term could be added to make it slightly more aggressive, but I never felt a need to do that.

Wednesday, June 08, 2011

Declaring multiple variables one line of code

Quiz time! Consider the following variable declaration in a C program:

float x, y = 0.0f;

What is the value of x?
















Answer: undetermined

This issue hit me, after so many years of ultra-explicit programming. A colleague way back in the UK taught me to prefer the explicit style of programming, since it's less likely to fall into traps like these. So coding programs in that style looks like:

char temp[ 512 ] = {"\0"};
int x = 0;
float y = 1.0f;

Everything gets initialized immediately after it is declared, so there is much less of a probability of picking up rogue / uninitialized values that way. This style also caused me to declare one variable per line.

I decided to take a shortcut after so many years for a quick experiment. Not just that... I decided to do this within a piece of embedded code running on a quadrotor.

The above shortcut led to the uninitialized value picking up the negative maximum value for an Arduino float: -2,147,483,648. Subsequently, this value was used in a calculation to add this particular value to an existing position. The result was a negative max float for latitude and longitude. This led to a quadrotor immediately hitting the limiter of the control system (-20 degree bank angle) and taking off to some undetermined location fractions after it was told to go into a position hold mode (where it stays in the same location in the xy plane at least).

After this line was changed to:

float x = 0.0f;
float y = 0.0f;

Things started working again. Since debugging on embedded systems is a huge pain in the *&(@#$, it took me some time to find and slap my head in disbelief.

This kind of thing is really easy to read over when you review code and definitely has the potential to have immense consequences... Another thing to seriously look out for.
( the assumption is that reviewers assume x = 0.0f as well, since it's part of the same line).

Proper code for multiple declarations in the same line look like this:

float x = 0.0f, y = 1.0f;

or:

float x = y = 0.0f;

Tuesday, May 31, 2011

Video annotations made easy

There's a project in the lab that looks at the use of some new technology and how this technology is best applied within a certain context (also perhaps, how people should change their behavior to improve the outcome). Anyway, what we will end up doing is observe a number of people and making video recordings. Throughout the experiment, these people will be talking to exchange ideas and point all noses in the same direction. At the same time, some interaction will occur through this technology, which is not easily captured on screen. However, because we deal with the tech directly, we can send events or information on a different channel, such that it can be superimposed back on video or at least related in time with certain points in the interaction.

I considered that for the purposes of analysis, it would be handy to make annotations on the video stream itself and refer to it later in time. The idea is that you can call attention or apply markers on the stream, such that particular events are easier to recognize and navigate to later. In essence, it's the same as what YouTube provides, except that we don't want these videos to be put on there yet, also because the duration of the video may be well about an hour or so.

ELAN is a nice tool that I found that has all the characteristics that we intend to use. It allows you to import an audio or video stream, which then can be annotated over the entire timeline for different events. As far as the technology events go, I've proposed to overlay that on the original video using a library called opencv. What you get is a static image that has all the events of the interaction between people, their audio, the things they did using the technology with annotations (in the form of subtitles) added by the experimenters. That way, the output video is a comprehensive output of the entire experiment, which can be replayed in good quality video players that can use subtitles in the SRT format.

Anyway, ELAN can also export to other text formats, including HTML or anything, which will also allow you to translate or transcribe entire videos and post a log of what happened somewhere. The only thing that it doesn't allow you to do yet is to output the whole thing to some directory, where you get a flash video file of some sorts, together with an HTML file + Javascript to be able to jump to each annotation from there.

Sunday, May 15, 2011

Arduino MAX7456 OSD & APRS

I've just finished up the hardware and software on an Arduino Duemilanove, connected to a MAX7456 OSD chip and implementing an APRS / AX.25 datastream over the audio channel. Video from a PAL or NTSC cam is fed into the OSD chip, which overlays the image with some relevant data variables. These variables then become visible to a human pilot in the form of some kind of HUD, allowing the pilot to make better decisions on throttle settings, landing, coming back home and so on.

The APRS / AX.25 link borrows most of the code for the signal sending from the Trackuino project. With the right filter and decoupling behind it and the right Fast PWM implementation, the signal quality is very impressive indeed (with quality meaning how perfectly the signal approximates sine waves at different frequencies).

The OSD used to be hooked up by a simple loop, where the OSD was temporarily turned off to refresh the video buffer and then turned on again. Needless to say, this results in flicker occurring at times and also characters sometimes appearing in wrong locations (due to the internal generation of VSYNC signals and the write operations being carried out at the same time).

The current hardware implementation uses INT0 on the arduino (Pin 2 on Duemilanove), which is connected through a 1K Ohm resistor to +5V and with a wire to the VSYNC pin on the OSD chip. This allows the chip to work already. Interesting points here:
  • I used to refresh the buffer every VSYNC trigger, resulting in no image whatsoever. The OSD now writes new information every x cycles or whenever anything has changed.
  • After every change to the buffer, you should re-enable the display by writing 0x0C to VM0.
The APRS / AX.25 link on audio was already seemingly working, but I couldn't get the data parsed for some reason. I suspected that the tools I was using ( multimon / soundmodem ) couldn't deal with the data or were expecting different formats. By closely inspecting the incoming audio signal however, I noticed some strange plateau's in the signal, as if the arduino stopped writing in the y-direction for a brief moment in time. Turned out that the VSYNC interrupt was interfering with the AX.25 modem interrupts, so I just made sure that either of these interrupts is active at any given time and wait for the other interrupt to finish before starting the other work. This shouldn't cause a huge performance problem for receivers downstream.

The RC circuit I use to clean the signal is in the config.h file of the trackuino sources:

// 8k2 10uF
// Arduino out o--/\/\/\---+---||---o
// R | Cc
// ===
// 0.1uF | C
// v

This reduces the 5V pin-out signal to 500mV peak-to-peak in the process of generating a very nice output. Together with the FastPWM implementation, this generates a very nice sine wave indeed.

It is very important that this signal is clean and sine-wave like. The slight delay caused by the VSYNC meant that, due to CRC checking at the RX end, the signal didn't validate. I caught on to this by being able to, once in a while, decipher a single slash '/', but longer strings couldn't be parsed at all.

The output of this signal goes to the mono audio in of the A/V transmitter on the craft. The audio signal is received by the receiver, is converted into a line-out, which is then sampled by the on-board ADC within my USB Hauppauge stick. The laptop can query the digital audio samples from the stick directly and analyze the signal to determine the frequencies. The frequency modulation is converted into a bitstream of 0's and 1's and eventually, the complete string rematerializes at the receiver end.

As said, there are some utilities for doing this on an Ubuntu computer. I've tried out soundmodem, which gives you a KISS / MKISS interface, but it's probably too complex for the simple purpose I need this for (which is to parse the string out of the data and hand this to some other process). I found 'multimon' as well in AFSK1200 mode and this does the job very nicely as well. 'multimon' was written in 1997 or so and works using the OSS interface on Linux, which is now deprecated (the old /dev/dsp interface ).

You can however load a set of alsa oss tools to simulate OSS devices and convert things on the CPU if needed. What I use to use multimon on an ALSA computer without having to modify any of the internal code:

> aoss multimon -a AFSK1200

This then outputs the data strings to the console.

So there you have it. One single, heavily used Arduino board to generate the OSD video stream and periodically (300ms?) send more telemetry (to your liking) to the ground station using APRS/AX.25 on the audio channel of the A/V transmitter. It is not a weight-effective means of doing this, because it adds one full arduino board to the weight, but it does handle all the processing quite nicely. You do need a 328P processor at least due to the size of the execution image that is to be loaded and the RAM that the code uses for internal buffers and so on.

Monday, May 09, 2011

HAM license

Well, nothing to do with the picture at the left actually, but I got my HAM license. This basically means that I can, as amateur and non-commercially, use some otherwise restricted frequency bands to perform research and other experimentations. One of the reasons to look into this relates to my work/hobby of dealing with UAV's. These require stable control lines, where delays in reception or processing over one second may incur a loss of the craft and also relates to getting direct video feeds from these aircraft using transmission equipment and sophisticated antennas.

Interestingly, the uav hobby seems to be ever increasing, especially recently when there are more kits around that are affordable and where one can get a craft in the air for under $200. There are also more self-built models in the sky and people are fooling around with new and old antennas and finding ways of making them easier or less expensive to build.

I don't have my callsign yet. I may at some point acquire some tx/rx equipment and start listening on some frequencies and explore this world a bit further. About the exam: 2 questions wrong out of 40. This is not a bad score at all. One question wrong about the use of capacitors in a feed line to a loudspeaker and the other one was I think something about legislation.

Monday, March 07, 2011

Faster than wind

How fast can you go in a vehicle going downwind in relation to the wind, using only the same wind for propulsion? Can you actually go faster than this wind, overtake it?

This is an interesting Wired story about someone who proves that you can achieve up to 3.5x or 2.8x the velocity of the wind. The real speed is governed by a number of factors, including friction and the strength of the vehicle itself:

http://www.wired.com/magazine/2011/02/ff_fasterthanwind/all/1

Tuesday, February 22, 2011

Hauppage USB live 2 on Linux

I've used the USB live2 stick for displaying analog (tv) video on Linux, when I was still on Ubuntu Lucid. Things worked ok back then, so kept the card. Then in a flash of non-inspiration, the "update-manager" appeared and I upgraded to the most recent version. The drivers immediately stopped working and these were pretty special at the time, because I compiled them to get it to work.

I use this stick in combination with a a GoPro HD camera, which in the same timeline I did the Ubuntu upgrade was upgraded to new firmware, which allowed it to stream TV out at the same time as recording video. Great feature! Unfortunately, since the new firmware allowed configuration settings for PAL, I decided to change that along with it. This appeared the real problem for the driver problems.

On Windows the driver is getting its output and all the lights work. So I figured it must've been a driver problem. Turns out that when I configure the GoPro camera to use the NTSC standard instead, I am getting output on Ubuntu Maverick and a decent one at that. For some reason, it appears as if the combination of the driver with PAL and GoPro output is incompatible with one another.

So, if you have a GoPro, attempt to use this together with USB Live2, try changing settings to NTSC instead and see if you get output that way. By the way, I'm using this in combination with an analog video receiver and yes, the same problems apply!

Sunday, February 20, 2011

Philosophy of Mathematics

In my line of work, I'm often confronted with people that face problems and want to have resolved. In some of these problems, mathematics are an essential part in the resolution of these problems. In some private part of research, I'm trying to find the real origins of intelligence and find myself going way back and forwards in time, space and mathematics, trying to come up with the answers. Some of the questions that are popping up sometimes is that there may be things incomplete about the language of mathematics itself, rather than failure in trying to find the right set or sequence of equations / formulas to apply. A lot of research over the past decennia in Artificial Intelligence has produced enormous amounts of very important and interesting applications, but none of these I find exhibit a strong sense of generality in their applications, which allow the same technique to be used over and over and over again in different situations. Most AI applications require hard-wired components of machinery in order to provide any solution.

This causes one to go back in time to try to find the origins of mathematics, in search for an answer whether maths by itself is (eventually) inherently limited and whether there's a bound for reality, a bound for mathematics or whether both of these worlds will run parallel forever (they are complementary forever), or whether the abstract thought being developed in mathematics will eventually diverge from reality by so much, that we're now dabbling in the abstract model itself to find both problems and solutions within that model, even there's no physical counterpart that would be subject to the abstract problem.

If you look at civilizations as they develop language, at some point in their language they start to associate a "count" of something with a body part. Some civilizations evolve this further to start using more abstract tokens like sticks to count beyond the maximum number of body parts you may have. In simple societies, it is unlikely you need more than the number of parts on your body to explain some concept (you could also modify the definition of how you refer to something). Those which do evolve, eventually use abstract representations to refer to some abstract notion as a "count". This "count" has no other concept other than our visual perception of being some number of concepts.

The numbers 0-9 as we know them now have evolved over a rather long period of time and came to us from India and Arabia. The number system is base-10, which allows for relatively very easy manipulation of the numbers during calculus. For this reason, they were eventually adopted and used over the Roman glyphs that dominated, for example, in Italy at the time.

The reason why numbers became useful are related to trade. The problem with trade is that you need to figure out how much to give of this for how much of that. So the practical problem required some way to refer to some 'count' of this and some 'count' of that, also some notion eventually that 'x' of this equals 'y' of that. Hence, the bartering and trading very quickly gave birth to the notion of equality and thus the equation.

Geometry evolved after that and served to be able to make rather precise calculations about areas of land, as well as how to carve and build appealing feats of engineering, build houses, bridges, etc. Even though not all forms and shapes could be accurately described at that point, there were some basic rules that could be used already to help out in the engineering effort. It is for these purposes already necessary to think in terms of half objects or fractional objects, like a third of a pie or two-thirds down a bridge. Engineering also required the use of unknowns

As you may notice until now, the roots of mathematics are housed in the manipulation of the 'counts' of things... how many meters, how many pears, how many of that for ... .

Then Newton came along and decided to use equations not just for static problems, but dynamic problems like apples falling from a tree. And here we also notice introductions of for example the differential equation. What the differential actually does is chop up some event over a larger period of time into many smaller parts, analyze their behavior in these smaller parts and develop a new equation that exhibits how the system changes over some time assuming that there is not significant deviation within that system. For a singular system, i.e. one that does not interact in the abstract model it is given with any other system, this kind of mathematics is very well suited for solving problems.

After Newton, a lot of new discoveries were made primarily on the side of physics. We do not only know how to count cows, trade land and figure out how far something is, but we can also use it to describe movement and how things move in space over time (however, with important assumptions). With Newton and the mathematics thereafter, people started to feed more abstract ideas into the language. Take into account that for every addition to this language, the deliberations have to be tested against the axioms of the language itself in order to provide consistency.

The problem with more abstract ideas is that some notions may have no reality counterparts, or that the elements that they describe in theory cannot be measured because they are either too small or too big (infinity is one such example). Just thinking about infinity itself and whether it existed or not has driven people mad (literally!).

Newtonian equations work very well for situations in which you assume a disturbance and the rest of the system is free of distortions for a certain length of time and this system has consistent and homogeneous properties (friction, etc.). But for different systems, even a very simple pendulum where you deal with oscillations, even the single system without a second interacting pendulum can only be practically computed to some degree of accuracy. That is, the real exact solution is the elaboration of some power series, depending mostly on the amplitude of the system.

So there exists already a rather simple dynamic system for which there's no real exact solution possible, because the power series extends towards infinity. If we use a supercomputer to compute the exact result, we'll never be able to calculate the result solution before the point in time we'll need it. And yet... looking at the real world and looking at a pendulum swing, there's the thing doing it. What's causing this inherent problem in mathematics, where it cannot be used with 100% accuracy on a pendulum (given some assumed mass), but can be used very precisely on the exchange of goods on a market?

There's something about mathematics that's horribly incomplete yet and it's something to do with recursion in mathematics. We need an ability to compute the outcome of recursion sets very, very quickly. The above demonstrates that the model of the real world of mathematics is really just a model and breaks down for certain practical uses of mathematics, depending on the complexity of the situation.

Tuesday, February 15, 2011

Chaos Theory

Chaos. The word itself evokes feelings of disorder, of things that are not orderly arranged, a jumbled up room full of stuff, stripes of paint seemingly without reason on a canvas, the results of the actions of satan, uninterpretable perceptions, everything that cannot be described with a simple description or looks untidy. The scientific meaning of chaos however is slightly different. It's not so much about being tidy, but about losing predictability and periodicity. The interesting thing is that from a scientific perspective mos
t, if not all, things around us have chaotic properties and are in one sense or another chaotically interfering with one another. Chaos theory researches the effect of sensitivity to initial conditions, which is when a very slight error in a volume, speed or other characteristic may lead to profound differences in the outcome of results over a longer period of time. Lorenz first discovered that certain systems are highly sensitive to initial conditions when he tried to predict the weather. He ran the simulation once and then printed results. At some point he wanted to verify his findings by running the algorithm again and to his astonishment, even after he verified that the numbers were the same, the outcomes were significantly different. The only difference was that the interpretation of the numbers by the computer were slightly truncated somewhere at the 1000th decimal number.

Normal periodic and linear systems do not typically amplify these errors, but just show a similar, linear difference in the outcome. Basically, your result is slightly off. What Lorenz found here is that after some point in time, the system started behaving completely differently from the initial run of the process. Sensitivity to initial conditions is what he discovered and he came up with a strong analogy for the phenomenon; the "Butterfly Effect". The analogy is that sensitivity to initial conditions could mean that a butterfly flapping its wings in Brazil could in theory cause a tornado in Texas to occur.

Other interesting discoveries were made by the russian Belousov, who mixed up a couple of chemicals together and discovered that it changed color to yellow, but then back again. Not only that, it was actually oscillating between clear and yellow. This phenomen had never been witnessed and at that time was seen as impossible. For that reason, his paper that he submitted to a journal was straight-out rejected. Even after a revisal nobody wanted to publish the results on the basis of lack of evidence. It was only years later after informal circulation in Moscow that eventually the results were picked up by Western scientists, who improved the experiments further and demonstrated that a petri-dish with a certain solution of chemicals may eventually demonstrate autonomous oscillation, autonomous meaning without induction of external disturbances. Thus, a system which switches between states in a temporal manner. The actual patterns that occur in such dishes *may* look like the following. The interesting bit is that this is dependent of..... the exact initial conditions!

As for the pattern itself... there's another great scientist called Benoit Mandelbrot, who's not a typical mathematician in the sense that he knew algebra very well :). He studied in Paris in the 2nd world war, so naturally the study was frequently interrupted. Also, he wasn't always that much interested in doing math tables and all that, but instead he had a great visual attention to detail. This made him look at coastlines and mountains and discover recurrences of smaller details in larger ones and come up with the idea of a very simple formula, describing a hugely complex shape overall. He called that a fractal:

The idea is that a very simple formula, z <=> z^2+c, gives rise to the picture above (calculated in the complex plane of course and where the result does not escape to infinity. The figure is self-similar in the sense that one can zoom in on the image and discover that the same shape is in many other different smaller locations at a fraction of the size, but in this case equal to the first one.

The interesting idea here emerges that very simple rules of interaction between elements can produce hugely complex systems at a larger scale. The complexity of the figure and the simplicity of the equation should give you some idea of that power. The relationship between the two has always been quite clear from an intuitive perspective, but reviewing these mathematical details suddenly changes that.

Chaos theory has put the world of Newtonian physics upside down. The idea of being in control of particular phenomena or occurrences just because we are able to predict it (to some extent).

The notions of chaos and order are not necessarily exclusive. In the majority of cases, when scientists mention chaos they do not mean "100% randomness" in their discourse, but they probably refer to: "some chaotic elements involved that deny a straightforward linear solution to the problem". This is because 100% randomness in systems yields no patterns whatsoever, just white noise. Therefore, there is a grey area between the notions of order and chaos and in many cases, when you feed energy into a system that behaves periodical, at some point you'll push it into chaos, where it'll behave unpredictably, but may eventually return to predictability and periodicity again, although that pattern of order may be different from the one you had before. Many systems, given a certain feed of energy, swing back between the two forever. This is what the Lorenz attractor at the top demonstrates, as well as demonstrating how the system is highly dependent on initial conditions (here, interpret this as infinitesimally small differences in the initial condition, the reciprocal of infinitely large).

What is different in mathematics when you compare Newtonian physics with Chaos Theory?
  • The expressions in chaos are very simple, but recursive.
  • Chaos math usually deals with interactions between systems or elements.
  • Newtonian physics require orderly systems to be able to predict what happens.
  • Chaos has its own cycles and may skip from apparent order to chaos and flip between the edge of chaos and back without warning.
  • When you put too much energy into chaotic systems, they become totally unstable and generate totally unpredictable results, leaning towards randomness the more energy you put in.

Saturday, February 12, 2011

New kind of science

I'm reading a book by Stephen Wolfram, which is called "A new kind of science". I picked up the title after viewing a number of very interesting lectures on YouTube from Robert Sapolsky at Stanford University about "Human Behavioral Biology". It is a privilege to be able to peek into his classes this way. One of the lectures is dedicated to cellular automata and he's explaining their relevance to biology. There's a book mentioned from Stephen Wolfram, so that's how I got there.

Anyway, there are very mathematical ways to explain how CA's work, but here's Wikipedia's one. One way to look at CA is also as a kind of state machine with many different states at very short intervals from one another, where these states are actually macro-states, the global sum of internal states of each cell. Because rather small changes in internal states can significantly affect the global outcome of the global state, the horizon over which one can make calculations to derive future states is rather limited. I.e., one needs to calculate every state inbetween in order to find the final answer.

Some three centuries ago we started discovering/inventing physics laws and formulas to make our lives easier. Nowadays these laws and formulas were used to construct airplanes and we went to the moon with them. Most of these laws come with rather large assumptions. Most of the time, it is:"Assuming nothing happens that introduces a significant error, we can derive our future position/velocity/acceleration by multiplying x with y over a z time period". We're just lucky that macro-objects like our vehicles behave that way in a consistent manner.

But looking at smaller interactions or larger systems like the weather, we can't use those laws as directly as that. The number of collisions and forces between objects make the entire thing so complex, that you can no longer work with laws that require these assumptions. So the complication is that you now have to represent many other bodies interacting with your system and calculate the state of this "universe" or "world" for each intermediate state, until you get to the goal state you want. Luckily the interactions are not usually really complex when you get to an appropriate level. Unfortunately, exactly knowing these interactions remains difficult in many cases and very slight differences in the "rule" can eventually produce very large deviations from the overall pattern.

It is the expectation that this kind of thinking will produce more understanding about the world around us, as there are so many processes that function according to these principles:
  • the billowing of smoke and vapour
  • pressure of gas
  • the way vortexes are produced by wings
  • interactions between neurons?
  • the structure of snowflakes
  • the ways how cells react to other agents?
Also really interesting is the way how such cellular automata can be used in combination with stochastic processes, the idea being that knowledge may not be complete for each "cell", but given their observations so far, they may like to assume certain facts about the overall structure and modify their behavior accordingly.

Saturday, January 29, 2011

TryCopter

Here's a video of a tricopter I was building:



There were some issues to resolve, but nothing much out of the ordinary. The biggest problem was ensuring the right firmware is loaded on the controller board and that this firmware functions properly. I bought the blue controller board from korea (www.kkmulticopter.com), but in my case the "blue board only" firmware created problems with yaw compensation. Most notably, the correction for pitch was the wrong way around, so if I were to fly this thing for real, it would have flipped over head over heels, so to say.

Other than that, there are loads of upgrades possible for this thing. My first approach was to ensure I can get this thing to fly. Other attempts will focus on more precision of the frame itself, possibly attaching my ArduPilot Mega controller board for GPS hold / altitude hold and those kind of applications and it would be very nice if I could use that board for more precision when flying.

Monday, January 03, 2011

Brazil's progress

Taking a bit of time off in Brasil, I'm really surprised by the changes that have taken place over the last 2-3 years. The first thing that one notices after disembarking an airplane is the large number of cars that are circling the roads nowadays. The cars themselves are no longer the usual about-to-break-down 9-15 year old Fiat Uno's anymore. Brasilians nowadays drive Honda Civics with the same options and luxury as in Europe (although Flex choice here is probably unique), the chinese are exporting their cars over here, you see large Hyundai 4x4's, Range Rovers, Mercedes, BMW and a lot more normal cars that are more reliable than 3 years ago. Indications that the global crisis that has hit Europe and US hasn't in the least bit hit anything in Brasil. There are now small funds available here and there for starting companies, the business itself is becoming less this-and-that, the people at the beach that used to walk by now have handcarts or Puchs, for those people that have made a name for themselves and/or sell reliable products.

In fact, the Brasilian analysts are commenting that yet another middle-class has surfaced in Brasil, which I somehow guessed due to the disappearance of the garbage/bottle collectors that used to roam the area around our appartment. It seems that the poorest of Brasil don't need to go as far in the city anymore in order to survive. My guess is that the poorest are now roaming around the outskirts of the city, closer to the poorer suburbs.

A disadvantage of the development is that these changes are taking place so fast that it is impossible to keep up with infrastructure. Building hospitals, roads, trains, metro's and all that takes time and there are likely not enough people to provide the capacity required to build all that even if the planning would be ready. Besides that, any type of construction requires engineers and engineers is exactly the kind of people that the world is short of.

The city I am in has also been built on the perspective that there are no serious changes in the economics of Brasil, for example considerable increases in salary or requirements of role/ability. The high-rise buildings are spread around the city and you could assume that each one of those appartments owns a car. The problem starts when those people purchase a second car for the wife, or even a third or fourth car for their children. One family, four cars. It is a good possibility in this city if the wages allow it, because many people still do not feel safe enough to walk on the streets or take public transport. The car as a status symbol, even if it's just a trodden down Fiat Uno of 6-year old, still better than taking a taxi. Probably, with the amount of traffic in the city, it's even a cheaper option.

The concern here is not so much the traffic on the roads or the traffic jams, but the result of a never-ending traffic jam in the city and what this does to people. Three years ago there were times in the city that you could just pass through and not be bothered much by any other car. Now people get delayed easily by 10-30 minutes per trip and this is costly to both their time available for family / business, as well as their health (nerves).

A small trip to the beaches in the south is a clear demonstration how in three years time, people are now reckless road warriors, competing for their own piece on the road. Even though the objective is to go to a tranquil place near the beach to relax after a long weekend, it seems that the haste of Europe has now been implanted in their brains and they seek to pass cars in front of them by any means possible, resulting in dangerous situations everywhere you go.

About every 10-20 minutes, there is a reckless driver behind, on the side or before you, trying to take another opportunity to move one car ahead in the long line of cars that everyone is part of. Family of mine driving in PE counted the number of hours on the road and the number of road deaths or very dangerous situations. They counted 6 such situations and have been on the road for a total of 6 hours.

One of the problems with such growth is that only few people drive defensively. Most drivers on these roads are offensive, they try to pass on every side, only thinking about how they left their homes 30 minutes late, then lost another 20 minutes in traffic and how to make up for that lost time. My advice to Brasilian drivers would be to take traffic into account, plan their days before and take safety seriously. From here on, the traffic in the cities will only get worse as there is still no end to the increase of car sales. The government has been very slow to respond to increase the road infrastructure and reliable public transport is inexistent.

So... even though the economic situation in all of Brasil and especially Pernambuco is very favourable, there are serious challenges ahead for the president and all governors to ensure that this growth will continue. One of those challenges is good, reliable public transport that also middle-class people will want to take advantage of. And invest in more road police work and make it work smarter. A lot of drivers are so badly mannered, they pass in convoys on the right and left in order to get ahead. They do that because there is no police stopping them. A good measure for people using the hard shoulders, reserved for ambulance and police is to be waiting at the end at a large terrain, where every individual can be fined in all tranquility. Who cares if they have to wait three hours before they can continue their journey?

Possibly, a number of new campaigns are necessary for awareness in road safety, educations in driving behavior and so on for the road situation to become more bearable for those drivers that are more serious and responsible.

Tuesday, November 30, 2010

Optimization in scheduling problems

The CSP solver talked about before is an effective way to calculate all possible solutions. Some problems however are either underconstrained or just have a very large number of possible solutions. In those cases, exploring the entire solution space may be very expensive; or certain application areas may be subjective to particular time windows in which the solution must have been developed (dynamic scheduling problems). Even in dynamic scheduling, there are differences with regards to the exact time window that is allowed. A scheduling system for shipping berths for example has a different allowed time window than a scheduling system for elevators.

The image shown here is a 'fitness' landscape. It's a bit of an imaginary landscape that displays how effective or costly a solution is. The peaks are desirable solutions, whereas the valleys are much less desirable. In this case, it's a one-dimensional graph, but for other solution spaces it could well be more of a 2D or even 3D space. The number of dimensions for the fitness landscape is actually determined by the number of cost functions you have.

This is where we get to the optimization part. A cost function is a function that determines the cost of a range of tuples that are (part of) a solution. This cost function is what guides the desirability of a certain solution and that is what basically drives the optimization. Ideally, one would like to find the best solution first. In reality, the best solution doesn't come first without a bit of back-tracking. Even worse, there is no guarantee in practical planners that the best solution will be found, only a solution that is 'good enough' given a certain threshold.

If you've paid attention, then I've talked about the use of a 'cost function', which actually only calculates the cost of a particular solution so far. So how does one actually form very good solutions? Because this sounds like it's more like trying out each possibility in turn until we're happy with the solution so far? This is why the cost function must be paired with a heuristic function. The cost function is used to calculate the actual cost/benefit. The heuristic function is used to calculate the expected cost or benefit for using the valuation in a particular domain variable over a slightly further horizon.

This is not exactly all. The cost functions do not have to be commensurate or agree with another. Sometimes a particular tuple choice is good for cost function A, but very bad for function B. So the balance between the importance cost functions must be determined prior to starting the solution process. Most cost functions are pretty linear, but it's also possible that continually preferring solutions that favour function A eventually raise the costs non-linearly, such that further in the solution space function B becomes cheaper than function A. Those are very difficult to solve.

There may also be other situations in which you don't want the ideal solution, but want to allow for a certain flexibility overall. For example, in a schedule for berthing ships where you expect changes to occur, you might want to favour a solution where a minor change in the schedule doesn't flip the entire schedule around, but where the change is constrained to one or two flips between tupelizations (because the more tuples are flipped due to the change, the more costly the change will have become).

Optimization is rather difficult to do effectively and it's an NP-complete problem. So either you arrange the computation power to go through all solutions, or find better methods to achieve proper solutions. There are two ways to do the optimization. You could try to do optimization at the same time as solving a CSP (basically, define the ordering of values for a variable when tuples are picked), or generate some schedule that is more or less good and then try to improve it through local search.

Local search basically means that you have a complete schedule, but pick two tuples of a set and flip valuations around (whilst preferably not violating the constraints) in the hopes of finding a schedule that is slightly better. Local search however, if you look at the image, is a bit tricky, because you may have to force the solution to go through a valley. And how can you tell whether the solution, when going up another hill, is actually going to be a solution with a higher peak than the one you had before? And if you're just going to try this out, how do you prevent the exploration of the entire solution space, which is what you wanted to prevent in the first place?

Basically, optimization is a bit like navigating a landscape in fog. You get only slight clues that there's a hill or a valley and at some point you must decide whether to carry on downhill to eventually find another monsterpeak, or stop searching altogether and call it your best solution. That is very difficult to do without a map. Constructing the map is equal to calculating the entire solution space.

Sunday, November 21, 2010

Sudoku, CSP and playing with sets

Sudoku is solvable as a constraint satisfaction problem. It is described as a problem where you should populate a grid of 9x9 tiles with numbers ranging from 1-9 in such a way, that there are no duplicate numbers in a row, column or local tile-block. Because an empty grid would allow you to derive any combination imaginable, the puzzle starts with a reasonable amount of number already filled in, usually in the order of thirty something. A naive approach in solving the puzzle uses a brute-force like mechanism: - Start from the first empty tile, determine which valuations can be made, continue to the next, etc... A much better and clever way to solve the puzzle is to find places where only one value is possible, fill this in and see if this modifies the state space, such that another single valuation can be made in a different location. I've taken some time to try to solve this puzzle using the CSP solver that is running on the database. The first naive approach took over an hour and still did not return a single solution. The second approach however worked out to a solution under three seconds. It can solve very easy puzzles as shown here, but also the hardest of them. Harder ones just take slightly longer, because there is less information. Here's how my state space is organized and queries operate:
  1. Create a table to denote the grid. Each record denotes a single tile as a column, row combination and also records to which block that tile belongs.
  2. Create another table that records per record the valuation for that single tile, the tuple.
  3. Inspect the puzzle and create tuple records for each already given number. These constrain the valuations you can make from there.
  4. Then launch this query every time there's still some tile left to evaluate:
select sc.col, sc.row, count(*) as count from sudoku_cell sc
left join tuple t on sc.col = t.col and sc.row = t.row, my_values mv
where mv.some_assignment not in ( select t.assignment from tuple t where t.col = sc.col )
and mv.some_assignment not in ( select t.assignment from tuple t where t.row = sc.row )
and mv.some_assignment not in ( select t.assignment from tuple t where t.block = sc.block )
and t.assignment is null group by sc.col, sc.row order by count asc;
The result is an ordering of tiles, described by the number of valuations that can be made for each specific tile, given the current state of the puzzle. Of course, when you have a tile there where one valuation can be made, that brings you one step closer to the solution.
How does Sudoku help us to understand human reasoning better and how computer algorithms work in comparison to human reasoning?
All this work with SQL got me thinking about the method that computers use in reasoning from the perspective of set theory. Reasoning in computers is highly dependent on set theory, especially when you use SQL like I do. Logic in computer programs are basically running sets through algorithms that determine if a member is part or not part of a set (unions, intersections, etc.). Some sets are made to relate to one another through attributes or keys from either member of each set.

When you want to do anything useful in SQL, you need discriminators that determine the scope of your set and then operations from one set on another. Sometimes the relationship is a parent-child or a direct relationship from one member to another, so you can join the elements together to form a superset. Sometimes you wish to eliminate those values that are apparent in another set without attempting to make a full join. A lot of logic in SQL revolves around the use of "WHERE x NOT IN" or "WHERE x IN" kind of statements. So how does this all work in general? No matter what the query, you typically start out in a form like:
SELECT x,y,z,... FROM TABLE abc;
and very likely, the next improvement to this query is an attached WHERE statement, which reduces the returned set to those values that do not violate the conditions. Another mechanism used for querying is to join tables together on some suggested relation and on the basis of that relationship, further limit the returned results (mostly on attributes in the rows of the related table). This allows you to make rather complicated queries like: "only return those cats that have more than 5 kittens" or "query all orders that have line items higher than threshold X, created between now and three months ago".

The reason for mentioning this is that it may help in the future to construct queries. If one set is empty, it cannot have any effect on another set, because they are fully disjoint. So in order to do anything useful, your query must return rows, at least one.

A tougher example is what I had to do for the Zebra puzzle. There are cases where you have a rule that discriminates members of a set. There may also be no rule. So you can't depend on any useful result returned from the rule query. The idea is then to return all rows unless there's a rule that dictates some should not be returned. The eventual query for solving the puzzle turned out as a very complex beast with multiple IN, NOT IN statements. It's probably helpful to describe them a bit here:

SELECT all colors that can be assigned to the current house being considered, where
  1. the color is not already used in a tuple,
  2. the color is not in any rule that specifically binds the color to a different house,
  3. If there's a rule that dictates the house I'm currently considering has a certain color (a set that is composed of one color), the color must be in that set (return 1). If no such rule exists, return all possible colors (so if no rule exists, allow any color as long as this particular rule is concerned),
  4. the color is not in a set, composed by rules that are active on houses to which I'm not a neighbor. So if a rule dictates that a house must be blue and I am not a neighbor to that house, then exclude blue from the set,
  5. the color is not in a set, composed by all colors that are determined by rules for which the rule dictates the neighbor of the currently considered house should have that color. So, if a rule dictates that my neighbor's house should be blue, then the currently considered house cannot be blue.
You can understand that such reasoning causes programs to explode in complexity. The logic interpreters like Prolog hide a lot of these details (backtracking, generation of possible values), but at some point you may want to start optimizing how sets are generated, which is where you get similar complexity. And you can only be effective when you know how exactly the interpreter is handling things for you.

In Sudoku there's a similar issue that is easier to understand, but not often modeled in solvers. For example, given the above specific sudoku puzzle, the computer finds that column 4, row 1 and row 7 both have one possible valuation. When I solved this puzzle by hand however, I was not immediately drawn to those possibilities, because there are lots of openings around those tiles, so instinctively not a place that could lead to a quick inference. What I did notice very quickly is that tile (9,8) can only contain a 7 because of the two columns 7 and 8 both containing a 7 and the rest of the tile block being populated. The constraints that the computer is using however still do allow a valuation of 1, 2, 3, 6 or 7.

This is the kind of knowledge of experts. Reasoning very quickly over many different sets of data, instantly reasoning over intersections, unions and so on. There are some visual combinations of elements that are very quick to analyze for humans, but which pose challenges for computers. Those quick analyses are very interesting to look at, because it's mostly expert knowledge that is not easily converted into some problem statement or constraint:
For a specific tile block, determine the set of possible valuations in that tile block that are still to be made. This is set X. Then count for each valuation the number of tiles it can be legally assigned to in the tile block. If there is a valuation with only one legal tile allocation, this is the placement to make.
In order to understand this, we need to have an idea about the relationship of one tile with another. This relationship is that one tile is placed in the same block as another tile. Limiting domains is a good way to increase performance if the cost of doing that is less than traversing the possibilities in brute-force. Such complicated relationships are not often modeled in reasoners due to their complexity, but as you can now see they are often and quickly used by human reasoners.

It's difficult to combine these results in one particular query or reasoning mechanism. Another way of looking at this is that they are different strategies for resolving the problem. The problem is only concerned with the tuples, the more there are found the better. Trying out different constraint combinations and understanding how at a higher level these change the solution space is a very important concern for such problem solvers. A downside of this is that the state space and complexity goes up significantly, but at the benefit of finding solutions much faster or much better than a standard CSP can guarantee.

Thursday, November 11, 2010

Constraint programming

I've blogged before about the difference between inductive and imperative programming. I've started to look more into constraint satisfaction problem programming, which actually able to provide you with solutions to a surprisingly larger amount of problems than you'd initially think. Typical examples of CSP solvers include the textbook examples like the n-queens puzzle, the region coloring scheme, the "SENDMOREMONEY" problem, the "Zebra" puzzle, eight number puzzle, Sudoku and so on. Real life examples tend to go down the route of static scheduling problems. I explicitly mention "static" here, because dynamic scheduling problems are those with the potential to vary significantly over a very short amount of time. A famous one for dynamic scheduling problems is the choice of the actions for a set of lifts in a busy skyscraper building. There are expectations from lift users to be served within a certain amount of time (requiring the insight in the required capacity at design time of course), but also the strategy of the elevators per individual and as a group needs to be adjusted.

But I digress, because static scheduling problems are rather similar without explicit time constraints on calculation duration. Typically, the values that you consider for CSP solutions are in the numeric, boolean or finite domain (sets). For example, you could have a domain that dictates whether a truck is used or not (boolean), how many hours it would take to perform a transport (integer), or in which timeslot or time of day a particular transport is initiated (set/finite domain).

There are various approaches to CSP. Many academic research papers mostly worry about the algebra and theory notations, mostly the functional and semantic correctness of the algorithm, which means that they mostly worry about constraint violation or not, not necessarily complexity or how long it would take to run the algorithm.

A naive approach starts from the brute-force approach. Just run through every possible combination in your entire domain set. Then verify for each combination you come up with, verify if any constraint is violated and then backtrack and try something else. This approach will take a very long time.

This is where it is useful to start applying as much knowledge as possible you have about your domain. I see the following concerns for resolving a CSP:
  • The primary concern is that the solution does not violate hard constraints.
  • The secondary concern is that it runs in reasonable time.
  • The tertiary concern is that it provides a good enough solution early on, ideally the first solution.
The concerns should be considered in the design and implementation. Actually combining variables from different domains together can be called tuplization, the action of constructing a list of tuples which form the solution. The domains may have the following properties:
  • Some domains have less elements than others and invoke more constraints. Start with the domain that has little elements, but most severely restricts future possibilities. Backtracking can be reduced by the order in which you process domains.
  • There is usually one domain, usually the first domain that you consider, which you only need to traverse once. So, if you have a domain {A,B,C,D}, then taking A and finding all combinations where A is valid, then B, then C will find you all the solutions. There is no further need to process {B,A,C,D}, {C,A,B,D}, {D,A,B,C}, etc... So traverse this domain once only in the order that is given.
  • Variables in domains may be ordered by (contextual) desirability.
  • Some domains have variables that can be used more than once, sometimes even unlimited, although they usually have some relationship with other variables in other domains that eventually reduces this domain as well.
Can you implement a CSP solver with an imperative programming language? Yes, but there are considerations to make on the approach, most specifically the algorithm you wish to use for exploring the search space. I consider that for CSP solvers that apply lots of knowledge benefit more from a depth-first algorithm instead of a breadth-first algorithm. The reason is that I do not think it is very effective to verify the constraints each and every time you wish to perform a selection, but you should maintain the state in memory as you pick the tuples out (and roll these back afterwards).

For example, consider a scheduling problem for a university. You have classrooms, professors, timeslots (hours) and students. These domains need to be combined in such a way that:
  1. Every student can follow all the registered courses
  2. All courses are taught the correct number of times per week
  3. A professor is teaching a course, but never teaching two courses at once
  4. A classroom is not used for two different courses at once
  5. There may be a preference for the time of day a course is taught
  6. Ideally, there are no hours between courses for any student on any given day (courses taught are consecutive)
  7. Some professors may have registered time off on particular days
  8. Some professors may indicate preferences for time off, but not as a hard constraint
  9. There may be preferences for using classrooms that are close together for consecutive courses
  10. Classrooms are typically used for particular departments of study
  11. Some classrooms are available for exceptions only, but are typically to be avoided (auditorium)
So the CSP here has a number of hard constraints (such things that when combined, would invalidate the overall solution), but also a number of preferences (those things that bear some cost when it needs to be used, but can be born or considered if there is no cheaper alternative).

In the above constraints, it is probably cheaper to maintain a large 'status list' for each room, professor, timeslot and student, such that it can be easily verified whether a tuplization, given the current state of the solution, would violate a constraint or not. Better yet, with a simple query, it is now possible to select only those variables from a domain which are still assignable, given the current choice of variables in another domain.

Many CSP solvers use C++ or Java constructs with huge libraries to maintain this state for you and attempt to expose a usable, although probably not complete, interface for you to manipulate. Any CSP engine should attempt to leave the manipulation of state space (those modifications you think you should perform to maintain a correct view of the situation) externally to the engine, but guide the user in the process of performing the tuplization. Or rather, it is rather easy to develop an engine that lets an application engineer insert a couple of domains or functions that provide these for every tuplization step, which also allows for pluggable points to perform changes when one tuple has been selected and of course steps to undo those changes.

Now connect a CSP engine to an SQL database, then you could use the functionality of the database engine (indexing, transaction management, transaction isolation, tables, type checking, flushing to disk, etc.). The SQL then allows you to query at each tuplization step what the remaining elements are for each domain. You only need to order those elements to improve the order of desirability of the selection you are making.

There are no guarantees for finding optimals here, so the ordering and other heuristics are still guesses overall (that a selection will not have severe negative effects on possible future selections, increasing the cost significantly). But you know that the selection process for variables in the domain only provide those variables that actually can be assigned sensibly, given the current partial assignment of variables in the tuple. This is why the order in which you process domains is important, it has consequences for how much knowledge you can apply in the model and the position where it can be applied.

Monday, November 08, 2010

Neural Dynamics

One of my main interests is understanding the dynamics within and between neurons that allows them to tune in to the behaviour of organisms which is in the interest of that organism at a higher level. In previous posts, I discussed a mechanism for these neurons to be excited by neurotransmitters released by a pre-synaptic neuron using, mostly, regulation of ionic fluxes (currents) through ion channels within the membrane.

The problem with these channels is that they are not linear in nature, but exponentially cause the opening of other channels (or inhibition).

Although it sounds like these are great mechanisms as a basis for intelligence, it's only the basis of operations for transmission of a signal from one end to another. Moreover, the channels do not typically behave the same way, because these are open for a different amount of time. So the voltage being measured is the resulting voltage from the sum of channels opening and generating some current. Each channel by itself can be associated with a particular probability for opening or closing and for a certain amount of time. Only at a macro-level when you assume, say, 1.000 channels, will it look like following some binomial or other probability distribution ( which is what also generates the nonlinear behavior at a macro level ).

So the fundamentals of neuroscience are providing a slightly more complete picture of the entire dynamics at work. Where the ion channels provide a mechanism for propagation, summing and integration of signals, it does not yet explain a useful integration and propagation as such. The synapse is still a very mysterious field of research with mostly speculation. It's still very much a mystery whether the famous Hebbian rule of "fire together, wire together" is a reality or more like some probabilistic phenomenon observed most of the time (but where the real dynamics are slightly more complicated).

Interesting discourses related to the power of integration of neurons can be found in the connections of axons from several pre-synaptics towards the dendritic tree of a post-synaptic one. Most neural models connect the axon more or less directly to the neuron cell body, thereby only allowing for the summation and integration of signals at the level of the soma, where all signals come together. The branches in the dendrite tree however may already perform a couple of integrations prior to the voltage potential reaching (or not) the ion channels near the soma, where presumably the action potential is actually truly activated and propagated.

The result here being that some signals, due to their proximity, can lead to very different results when added together at a local level, rather than at a global level. The underlying reason is that an inhibitory signal can entirely cancel out another signal of different magnitude (so the result is not necessarily mathematically correct). A good example of these effects is by looking at formulas in maths. Integration at the level of the soma would equate to a formula like:

Y = A - B + C + D - E

But integration at branching points in the dendritic tree can cancel out any prior summation of positive signals just by applying a signal of similar magnitude on a place higher up (lower up?) in the branch, so you could get:

( C + D - F - G + H + K + L - M - ....... whatever .... ) - E = 0
Y = A - B

The difference here being that the placement of connections in the dendritic tree is important and that there is only a certain range available for excitations or inhibitions. So besides 'just' integration of signals, this suggests that certain more or less 'logical' operations may also exist, which can be very useful for more complex separations of data and signals. It must be said that this tree is not necessarily typically "logical", as some effects have been noted where activations at the remotest end of the dendritic tree cause increases or decreases of the action potential at about 200-300 um into the axon. So the real effects of how neurons connect to one another's tree is still food for thought.

All this is speculation of course. The most useful thing that a neural algorithm needs is a better learning algorithm. Most of these algorithms in classical neural nets are back-propagating ones. This means you measure at the output, calculate the error, then back-propagate this error within the network to follow some kind of gradient. You need the derivatives from the neuron activation functions for this to happen.

If you want this to work in nature, you'd need a second brain to calculate the error and then have this applied inside the network. Hardly plausible. Somewhere is a mechanism at work which has local knowledge only and which adjusts the synaptic efficacy accordingly. This adjustments taking a certain amount of time and which is highly regulated by Long Term Potentiation (the ability of a neuron to become more excitable over a longer period of time). It seems that all in all, there are certain time windows where a neuron starts to synthesize proteins, which eventually modify the behavior of the neuron, change the structure or otherwise influence the synaptic gaps (by making more synaptic vesicles for example).

Saturday, October 16, 2010

ZeroMQ

I'm evaluating a couple of products for a larger project at work. The project will use at some point some kind of distributed storage, which may possibly be filled by the "ceph" project. Although it is experimental, there are a good couple of features that work already. For these evaluations, I've looked at some other work that has been done in this area. Most notably of course is the work that Google has done (GFS, Chubby, Percolator and BigTable). Some of the concepts described there are also implemented in Ceph, most specifically the Paxos algorithm for reliable replication.

Distributed storage is great for anything you'd like to query and which should be available 3-4 seconds after the data is "created" (although it's very likely created earlier). Distributed storage though is not a very good basis for broadcasting/multicasting/unicasting data as fast as possible after it was produced, because clients end up polling the file system for changes. For efficiency's sake and your own sanity, it is then better to use some kind of message queue. Two main architectures here: "bus" and "broker". The bus is basically a local subnet broadcast, where everything attached to the bus will have to parse messages and discard them if there is no interest. The broker(s) can be configured to receive messages from producers and route them through some broker network, reducing the number of times messages are copied and thus get re-transmitted through a separate link. Buses are useful only if you want all servers to know about the data, or the majority of them. Brokers are useful if you have geographically dispersed locations, want full control on how data is retransmitted, etc... Some brokers can also act more like "hubs", if you follow the "pubsubhubbub" project.

Sidenote: if you can avoid 'realtime' and mq altogether and do it through some file system, I'd recommend it. The concepts are simpler, it's easier to deal with faults and should you need any group locks, then the file system, even the distributed one called ceph, will be able to provide that for you. A mq puts the onus on the client for data caching, storing, reordering and all that. So file-based applications are always easier to write (at least from the client perspective :).

A quite complete evaluation of message queues was made by SecondLife. Note what is said about "AMQP". I believe that standards should evolve from things that work and not the other way around. For more information, check out:

http://bhavin.directi.com/selecting-a-message-queue-amqp-or-zeromq/

http://www.imatix.com/articles:whats-wrong-with-amqp

I've downloaded 0MQ and decided to give it a spin. The first thing I did was visit the IRC channel on a saturday and there were 50 people in there. That's usually a very good sign it's quite popular. There's a good chance that 0MQ is getting some serious attention soon. It may not be the absolute topper in performance speed, but it may be best if you're looking for flexible solutions, prototyping and esxperimentation. Having said that, if you're not running a super-duper high-performance site that needs to squeeze all the juice of your CPU's and NIC's, ZeroMQ will do just very fine for you, no problems whatsoever.

To set the expectations right... it's a bit more of a library for internetworking your applications together using multicast/tcp/ipc protocols, but that's already a big gain if there's a library that does that for you. This is typically a layer where many developers think they want something special, but ends up being the same requirement like everybody else's. Relying on a 3rd party lib that's widely used everywhere, and thus tested, is a very good decision. The only thing you end up doing is writing the application or service specific implementation and the message marshalling stuff. The library does the rest.

For anyone doing Enterprise messaging, 0MQ won't give you much yet. There are no tools to replay messages, retrieve them from error logs and what have you (or development tools). You may need something like OpenAMQ instead or RabbitMQ. To be honest, you do not necessarily need anything more complicated other than 0MQ if you develop everything in house.

Many services nowadays use XML/XSD to specify message formats. My main gripe with XML is that for too many people, it's about dealing with format instead of function. The issues with namespaces and all these other things make XML a really big beast to handle. Read _message matching_ to get some ideas where this will go wrong. Delayed brokers eventually slow down your entire business, make brokers unreliable, cause delays in some transactions that need to go fast, or negatively impact other processes that run on the same machine, requiring you to set up 2 brokers with double the probability something goes wrong... etc... Better get rid of it, move on and separate 'meaning' from 'transmission' and then verify things later. No need to encapsulate each message with the entire ontology each time a message is sent. I have a couple of interesting ideas in this respect that I'll share later as a research publication perhaps.

Update: 0MQ isn't without 'issues', but as far as I could determine so far there aren't any serious bugs in the code like memory leaks or reconnects, etc... I found two issues so far:
  • Messages are not being throttled at the server side. So if you look at the weather server example, which sends a lot of messages as fast as possible, under the water these messages actually get piled up in a list for the I/O subsystem to transfer them asynchronously. If the I/O subsystem simply cannot keep up, then you'll deplete your memory resources very quickly. The solution is to add high water marks or swaps, or use other methods for throttling the throughput of messages.
  • zmq_poll works, but because it assumes you're listening on multiple sockets, the idea is to visit each socket pool as fast as possible to collect any new messages that may have arrived. You then get one message per call and some kind of interleaving between each socket pool (if they're both really fast). Although this sounds nice, the underwater code assumes that you do not want to maintain any kind of "sleep" or other function to give back some CPU time for other processors. So, when you start 10 clients as in the examples implementing the zmq_poll, no client will yield and they all try to get 100% CPU time. If your client app can deal with it, the workaround is to embed a simple 'x' ms sleep in there. I recommend you sleep only when the last cycle didn't actually read any messages (no event was set).

Sunday, October 10, 2010

Ion channels of excitable membranes

I've just finished reading a book about ion channels in excitable membranes. Some types of excitable membranes are neurons, hence the interest. The kinetics of these types of cells are really interesting to try to understand. The more complicated or integral parts of sensory processing (and what this means) are performed in such cells.

The different types of channels and subtypes thereof have over time evolved by responding to particular messages or refined their function to respond better to what is happening in the environment. As this blog is not academic, I can voice some gut feelings / hypothesis here without bothering too much about scientific grounding and such. Most of the time, people philosophize over the function of the brain using analogies with existing machineries, comparing it to a computer and so on, but most of the time it becomes really difficult to trace this down towards actual cell function.

I think computer scientists made a bit of a mistake to make sweeping generalizations over the function of a neuron some 60 years ago. The attempt was made to map the function of neurons to something that could run on computer hardware. It started with a model where neurons, because they emitted a potential ( a pulse?! ), could be compared to logic building blocks which either emit a 0 or 1. Just like electronics. The "1" in electronics is basically the 5V of action potential that you'd normally put on a component to communicate a signal.

At some point, the "binary" neuron made way for the sigmoid neuron (so the 'processing kernel' was simply replaced) and this led to networks that were slightly more capable of performing some kind of function. At the moment, a lot of research is undertaken on Spiking Neural Nets (SNN), but there's still not a ground-breaking success in those networks.

I think the reason is that classical nets didn't pose any constraints on the timing of events, because they were mostly used for situations in which each state was information complete and where it was possible to derive the entire output from the combination of inputs (or let's make the output some approximation, as long as it worked, it was fine). Spiking nets do require specific timing constraints and there's not enough knowledge yet to support how such neurons should function over the domain of the signal and time to respond appropriately.

The refinement of using a sigmoid kernel (or tanh kernel) over a binary one is an important one already. The binary kernel was so abrupt in the change, that it was only useful in very specific situations. The sigmoid kernels are more useful, because you can generate proper outputs over a larger dynamic range. But the use of a replaced kernel hasn't been fully exploited yet.

The ion channels of membranes come in roughly three types:
- excitatory (generating the potential)
- regulatory / rectifying (attempting to establish equilibrium)
- modulatory, or acting over a longer time period, having an effect on the excitability of the cell

Classical nets are generally built with some assumed kernel in place and all kernels having the same configuration or parameters. The modulatory effects are not modeled in any way and the calibrati0n of the network is highly focused on the calculation of the weights, assumed to be the efficiency in transfer of neurotransmitters in the synapse.

The book I am reading demonstrates that the fast excitatory and regulatory actions themselves can be modulated somehow (this is like saying that the sigmoid function changes its shape), but that over time or multiple "calculations", this shape can also be modified on the basis of the output of this shape in previous steps (so the output of the kernel is changed as a function of the output of the same kernel in previous steps through some kind of accumulation function).

The classical nets seem very useful to have some alternative, mathematical model using neural networks for very complicated problems, but their abilities may be enhanceable by looking at biologic models in more detail. Neurons do not always function the same way, but you need to look at their behavior over time to see the longer-term effects of repetitive firing, the way how other inputs may influence their behavior (neurotransmitters) and either increase excitability or decrease it (or even suspend it).

However, I am convinced that networks that need to perform real-time tasks, or otherwise tasks where time is explicitly a concern can only be built with networks where this type of modulation and excitation is explicitly built in. The classical nets were never built from this perspective, but they remain interesting for classification or historical data analysis. The controllers (robotics?) of tomorrow and so on should attempt to understand more the dynamics and kinetics of the ion channels in neurons and the ability of neurons to time things.