Blackboard Design Pattern: A Practical Example - Radar Defense System

Blackboard Design Pattern: A Practical Example - Radar Defense System

This article presents a WPF C# example of the Blackboard design pattern, available on TechNet Gallery.

http://gallery.technet.microsoft.com/Blackboard-Design-Pattern-13a35a7e

It discusses the concepts of the design pattern, and highlights points of interest for C#, WPF developers.



Introduction


The Blackboard pattern is a design pattern, used in software engineering, to coordinate separate, disparate systems that need to work together, or in sequence, continually prioritizing the actors (or knowledge sources).

The blackboard consists of a number of stores or "global variables", like a repository of messages, which can be accessed by separate autonomous processes, which could potentially be physically separate. A "controller" monitors the properties on the blackboard and decides which actors (or knowledge sources) to prioritize.

The first five years of my 22 year career were spent in military radar detection and civil aviation. Radar data is enormous and it needs to be processed into something that can be analyzed in "real-time".

The biggest job by far was simply converting the colossal amount of radar data into computer data, which would be split over multi-processors - hundreds or thousands of individual processors, each analyzing their own part of the spectrum. Converting "real time", constantly incoming, raw radar data into usable computer data is by far the most processor intensive operation of this system. In my day we used multi-processors (hundreds/thousands of individually wired processors in racks in military vehicles or sprawling processor rooms. We even used a specialized language called RTL2 and M68000 "machine code inserts" (snippets of manually crafted machine code) , to process in real time, where every processor cycle counted.

As the data was coming in with increasing granularity, so we could start analyzing the data for patterns. As patterns emerged, they could be checked against known patterns until a small set of possibilities remained.

Then other processes could test the data or actual target further until a consensus between actors (or knowledge bases) was reached. Finally, the result would be acted upon, like an indicator in an output console, showing a plane on it's flight path, collision warnings, threat warnings, etc.

This of course sounds very similar to the Blackboard pattern, so I decided to share this project with you to demonstrate some of the concepts.

http://gallery.technet.microsoft.com/Blackboard-Design-Pattern-13a35a7e
 

 

Return to Top


The Concepts

In this example, the controller runs in a loop, iterating over all the Knowledge Sources that are active, and executing each.

The Blackboard Pattern defines the controller as the decision maker, as to WHICH Knowledge Source to execute and in what order. In this project that is represented simply by a "Priority" enum which orders the Knowledge Sources. For example the WarMachine is top priority and executed first, so any known threats are acted upon, before any decisions are made.

The Blackboard Pattern states that each Knowledge Source is responsible for declaring whether it is available for the current state of the problem being analyzed. This could in fact be an autonomous process, as the Knowledge Sources could monitor the Blackboard directly, but in this example there are multiple problems (detected objects) being analyzed, so each Knowledge Source has an IsEnabled property, which is set if there are any valid objects on the Blackboard.

The Blackboard Pattern declares that the controller iterates over the Knowledge Sources, each taking their turn at the problem. As this is a multi-problem Blackboard, I decided to stick as closely to the original concept and let each active Knowledge Source iterate over all the problems/objects that meet it's execution criteria.

Some descriptions of the Blackboard Pattern include a callback delegate method, which the controller would then act upon to select the next best problem solver (Knowledge Base). There is a good argument that each of these modules could be working autonomously, and reporting back any changes that are needed. This would be a change to the controller concept of the Blackboard Pattern, so I stuck to a flat turn-based system. The only exception being the Radar module, as it is more of an "input" for the Blackboard, rather than an "actor" on the data.

 

Return to Top


The Project


This document describes the project available for download at TechNet Gallery

http://gallery.technet.microsoft.com/Blackboard-Design-Pattern-13a35a7e
 

MainWindow


The project only has one user interface, which presents the Blackboard data as a visual representation of the objects being analyzed.
 

The ListBox


In MainWindow.xaml is a simple ListBox. However, the ItemsPanel has been converted into a Canvas for it's ItemsHost, so that items can be positioned by X & Y, rather than just a list.

<ListBox ItemsSource="{Binding blackboard.CurrentObjects}" ItemsPanel="{DynamicResource ItemsPanelTemplate1}" ItemContainerStyle="{DynamicResource ItemContainerStyle}" ItemTemplate="{DynamicResource ItemTemplate}" Margin="20,20,20,10" Foreground="#FFDE6C6C" >
    <ListBox.Resources>
        <ItemsPanelTemplate x:Key="ItemsPanelTemplate1">
            <Canvas IsItemsHost="True"/>
        </ItemsPanelTemplate>

 

The Item Container


The ItemContainer is used for positioning (Canvas.Left & Canvas.Top), NOT the ItemTemplate itself.
 
<Style x:Key="ItemContainerStyle" TargetType="{x:Type ListBoxItem}">
    <Setter Property="Background" Value="Transparent"/>
    <Setter Property="HorizontalContentAlignment" Value="{Binding HorizontalContentAlignment, RelativeSource={RelativeSource AncestorType={x:Type ItemsControl}}}"/>
    <Setter Property="VerticalContentAlignment" Value="{Binding VerticalContentAlignment, RelativeSource={RelativeSource AncestorType={x:Type ItemsControl}}}"/>
    <Setter Property="Canvas.Left" Value="{Binding X}"/>
    <Setter Property="Canvas.Top" Value="{Binding Y}"/>
    <Setter Property="Template">
        <Setter.Value>
            <ControlTemplate TargetType="{x:Type ListBoxItem}">
                <Border x:Name="Bd" BorderBrush="{TemplateBinding BorderBrush}" BorderThickness="{TemplateBinding BorderThickness}" Background="{TemplateBinding Background}" Padding="{TemplateBinding Padding}" SnapsToDevicePixels="true">
                    <ContentPresenter HorizontalAlignment="{TemplateBinding HorizontalContentAlignment}" SnapsToDevicePixels="{TemplateBinding SnapsToDevicePixels}" VerticalAlignment="{TemplateBinding VerticalContentAlignment}"/>
                </Border>
            </ControlTemplate>
        </Setter.Value>
    </Setter>
</Style>

 

The Item


The ItemTemplate defines the object, just an Image and a couple of TextBoxes, all wrapped in a colour-changing Border (for safe or threat).

There is also a countdown TextBlock for DistanceFromDestruction, which counts down until the War Machine (planes, missiles) reaches any targets identified as threats.

<DataTemplate x:Key="ItemTemplate">
    <Border>
        <Border.Style>
            <Style TargetType="{x:Type Border}">
                <Style.Triggers>
                    <DataTrigger Binding="{Binding IsThreat}" Value="true">
                        <Setter Property="Background" Value="Red"/>
                    </DataTrigger>
                    <DataTrigger Binding="{Binding IsThreat}" Value="false">
                        <Setter Property="Background" Value="Green"/>
                    </DataTrigger>
                </Style.Triggers>
            </Style>
        </Border.Style>
        <Grid Margin="3">
            <Image Height="48" Source="{Binding Image}" />
            <StackPanel Margin="0,0,0,-30" VerticalAlignment="Bottom" >
                <TextBlock Text="{Binding Type}"/>
                <TextBlock Text="{Binding Name}"/>
            </StackPanel>
            <TextBlock HorizontalAlignment="Right" TextWrapping="Wrap" Text="{Binding DistanceFromDestruction}" VerticalAlignment="Bottom" Width="Auto" Visibility="{Binding IsThreat, Converter={StaticResource BooleanToVisibilityConverter}}"/>
        </Grid>
    </Border>
</DataTemplate>

Code Behind / ViewModel

 
The code behind simply instantiates the Controller and Blackboard components, and sets itself as DataContext (for any bindings) - the code-behind thereby acting a bit like a lazy MVVM ViewModel implementation.

public Blackboard blackboard { get; set; }
Controller controller;
 
public MainWindow()
{
    InitializeComponent();
    DataContext = this;
 
    blackboard = new Blackboard();
    controller = new Controller(blackboard);
 
}

As mentioned above, the signal processing part of the application is the most time consuming, and when you run the application, you will notice some objects reach the top of the screen before they are identified. One good reason to use this pattern is it's extensibility, as you can bold extra modules on with ease, even as it is running. To demonstrate this, a button calls a method in the constructor top add extra Signal Processors, which obviously improves the speed objects are identified.

private void Button_Click(object sender, System.Windows.RoutedEventArgs e)
{
    controller.AddSignalProcessor();
}

IObject, BirdObject, PlaneObject, RocketObject, ObjectBase


As all objects that are captured by the radar can have the same set of properties (name, x, y) there is a base class called IObject:

public interface IObject
{
    ObjectType Type { get; set; }
    string Name { get; set; }
    WriteableBitmap Image { get; set; }
    bool? IsThreat { get; set; }
    ProcessingStage Stage { get; set; }
    int X { get; set; }
    int Y { get; set; }
 
    IObject Clone();
}

Bird, Plane & RocketObject represent the three object types we can detect, but to save time, they all derive from ObjectBase and I define them in the Radar module:

AllObjects = new List<IObject>
{
    new BirdObject(ObjectType.Bird, "", new WriteableBitmap(new System.Windows.Media.Imaging.BitmapImage(new Uri(@"pack://application:,,,/Media/Bird.bmp", UriKind.Absolute))), false, false),
    new PlaneObject(ObjectType.Plane, "", new WriteableBitmap(new System.Windows.Media.Imaging.BitmapImage(new Uri(@"pack://application:,,,/Media/Plane.bmp", UriKind.Absolute))), false, false),
    new RocketObject(ObjectType.Rocket, "", new WriteableBitmap(new System.Windows.Media.Imaging.BitmapImage(new Uri(@"pack://application:,,,/Media/Rocket.bmp", UriKind.Absolute))), false, false),
};

This is a little lazy I admit, as each object could encapsulate it's own data, but this small project is not design best practice, just design pattern concept ;)

So we have different objects and their known images. if you look at the images you will see they are similar, but slightly different:



Incoming Object


Once an object is "detected" by the Radar module, a new IncomingObject is added to the Blackboard's CurrentObjects collection. The actual object is hidden in a private property of the IncomingObject, which the Knowledge Sources will interrogate, to simulate the process of detection, analysis, identification and potentially it's destruction!

public IncomingObject(IObject obj)
    : base(ObjectType.Unknown, null, null, true, null)
{
    actualObject = obj;
    ProcessedPixels = new bool[16, 16];
 
    //Paint the image as all red to start with
    Image = new WriteableBitmap(48, 48, 72, 72, PixelFormats.Bgr32, null);
    int[] ary = new int[(48 * 48)];
    for (var x = 0; x < 48; x++)
        for (var y = 0; y < 48; y++)
            ary[48 * y + x] = 255 * 256 * 256;
    Image.WritePixels(new Int32Rect(0, 0, 48, 48), ary, 4 * 48, 0);
}

As shown, the "known image" begins as red, as it has not been processed at all yet.

Knowledge Sources


Knowledge Sources represent the brains of the system, each specializing in a different stage or part of the problem. In our example, this is presented as follows:
  • Signal Processing - The biggest job of number crunching the radar data (eg spectrogram analysis) into digital data
  • Image Recognition - Comparing the part processed image with known signatures
  • Plane Identification - "Hand-shaking" with onboard computers, requesting voice contact, checking flight paths - basically deciding if friend or foe
  • War Machine - if a Rocket or hostile Plane, the military take over and decide how best to deal with the target (Missile defense, scramble rapid response fighters)

They could be completely separate systems, located in separate places, communicating through secure services. However, all they would need to co-operate in the system is a shared/common interface, as outlined as an essential part of the Blackboard design pattern.

public interface IKnowledgeSource
{
    bool IsEnabled { get; }
    void Configure(Blackboard board);
    void ExecuteAction();
 
    KnowledgeSourceType KSType { get; }
    KnowledgeSourcePriority Priority { get; }
    void Stop();
}

The first three lines here are as per the Blackboard design pattern.
  • IsEnabled is set if there are any problems that this Knowledge Base can execute upon.
  • Configure sets up any specific parameters or data that is offered by the controller to help solve the problem. In my multi-problem example it is not used, as each Knowledge Source interrogates the objects directly, from the Blackboard.
  • ExecuteAction is the method that makes the Knowledge Source perform "do it's business" on the problem(s)

Signal Processor

This is the first Knowledge Source to "act upon the problem", in that it takes the raw radar data from the "Incoming Objects", as presented on the Blackboard, in the CurrentObjects collection, which the radar is reporting to. As explained, this is by far the most processor intensive part of the system.

To represent this, I have added a level of granularity into the signal processor, allowing it to only process one small "block" of pixels from a random square of the image. This means that if the random selection is unlucky, it can take many attempts, before the image processor returns enough to identify the object. This is demonstrated in the ProcessAnotherBit method.

public override bool IsEnabled
{
    get
    {
        for (var ix = 0; ix < blackboard.CurrentObjects.Count(); ix++)
            if (blackboard.CurrentObjects[ix].Stage < ProcessingStage.Analysed)
                return true;
 
        return false;
    }
}
 
public override void ExecuteAction()
{
    for (var ix = 0; ix < blackboard.CurrentObjects.Count(); ix++)
        if (blackboard.CurrentObjects[ix].Stage < ProcessingStage.Analysed)
            ProcessAnotherBit(blackboard.CurrentObjects[ix]);
}
 
void ProcessAnotherBit(IObject obj)
{
    int GRANULARITY = 16;
    int blockWidth = obj.Image.PixelWidth / GRANULARITY;

      

Copying Between WriteableBitmaps

ProcessAnotherBit acts upon the image, which in WPF terms is a WriteableBitmap.
The method copies the known/shown image (to be worked upon) into an array of bytes, representing the image pixels.

int stride = obj.Image.PixelWidth * obj.Image.Format.BitsPerPixel / 8;
int byteSize = stride * obj.Image.PixelHeight * obj.Image.Format.BitsPerPixel / 8;
var ary = new byte[byteSize];
obj.Image.CopyPixels(ary, stride, 0);

And a similar array for the hidden (to be analyzed) image:

var unk = obj as IncomingObject;
unk.GetActualObject().Image.CopyPixels(aryOrig, stride, 0);

It then chooses a random square from "aryOrig" and copies the pixels into the known/shown byte array "ary":

for (var iy = 0; iy < blockWidth; iy++)
{
    for (var ix = 0; ix < blockWidth; ix++)
        for (var b = 0; b < 4; b++)
        {
            ary[curix] = aryOrig[curix];
            curix++;
        }
    curix = curix + stride - (blockWidth * 4);
}

And finally returns the updated array to the actual WriteableBitmap:

obj.Image.WritePixels(new Int32Rect(0, 0, obj.Image.PixelWidth, obj.Image.PixelHeight), ary, stride, 0);

 

Image Recognition

This knowledge Source is responsible for trying to figure out what the pixilated image is. This is done on every "pass" of the data, as the image takes form. Every time a block of pixels is added to the known image, it is compared against known images to see if it now only matches ONE of the images. Although not shown in this simple example, it could also trigger if all remaining images are hostile, allowing the War Machine to get involved before the image is even fully analyzed.

Comparing Pixels

This is an ugly piece of byte crunching code not worth documenting, except for the actual ARGB comparison:

for (var ix = 0; ix < blockWidth; ix++)
{
    var argb1 = (ary[curix + 1] * 256 * 256) + (ary[curix + 2] * 256) + ary[curix + 3];
    var argb2 = (aryKnown[curix + 1] * 256 * 256) + (aryKnown[curix + 2] * 256) + aryKnown[curix + 3];
    if (argb1 != 255 * 256 * 256 && argb1 != argb2)
    {
        nomatch = true;
        break;
    }
    curix += 4;
}

As you can see, it is iterating through the array of bytes, pixel by pixel (4 bytes at a time). This code specifically checks the RGB values for a match.

If the detection code finds only one match remains, then the data is retrieved for the hidden object, representing the "found you" moment, when you pull the relevant data from lookup databases, and potentially representing many other Knowledge Sources which may have been watching the Blackboard for such updates.

if (matches.Count() == 1)
{
    obj.Type = matches[0].Type;
    obj.Name = matches[0].Name;
    obj.IsThreat = matches[0].IsThreat;
 
    obj.Image = new WriteableBitmap(matches[0].Image); //Create new image instance
 
    if (obj.Type != ObjectType.Plane)
        obj.Stage = ProcessingStage.Identified;
    else
        obj.Stage = ProcessingStage.Analysed;
}

 

Plane Identification

This Knowledge Source is just an example of another analyzer layer that could process the data further. We have BirdObjects (safe) and RocketObjects (hostile) but we also have PlaneObjects, that could be either, depending on further analysis. In this module's Execute method, it emulates the process of further analysis, whether that be initiating a hand-shake protocol to onboard computer identification systems, a manual contact attempt from air traffic controllers, and checking the resulting data against published flight paths.

This is a good example where a callback method would be used, as further analysis could take "human time", which is of course, the slowest of all.

In this simple example, this is represented by further extraction of data from the hidden actual IObject, within the IncomingObject:

for (var ix = 0; ix < blackboard.CurrentObjects.Count(); ix++)
{
    var obj = blackboard.CurrentObjects[ix];
    if (obj.Stage == ProcessingStage.Analysed && obj.Type == ObjectType.Plane)
    {
        var unk = obj as IncomingObject;
        var actual = unk.GetActualObject();
        obj.Name = actual.Name;
        obj.IsThreat = actual.IsThreat;
        obj.Stage = ProcessingStage.Identified;
    }
}

 

The War Machine!

This final Knowledge Source represents one possible "solution" to the problem :)

To add extra "peril" to this example, it takes three seconds (passes) for the military to "respond and react" to an object that is identified and labeled as hostile.

With each pass of the War Machine, each 'military response' gets closer to it's target. This represents the delay it takes for Missile Defense Systems to respond, SAMs or "rapid response" type fighter jets to scramble and intercept the target.

Drawing on a WriteableBitmap

The "final blow" is represented by a little piece of WriteableBitmap manipulation, to draw a cross over the image:

public override void ExecuteAction()
{
    for (var ix = 0; ix < blackboard.CurrentObjects.Count(); ix++)
    {
        var obj = blackboard.CurrentObjects[ix] as IncomingObject;
        if (obj.IsThreat != null && obj.IsThreat.Value && (obj.Stage != ProcessingStage.Actioned))
        {
            if (obj.MoveHitsTarget())
                DestroyTarget(obj);
        }
    }
}
 
private void DestroyTarget(IncomingObject obj)
{
    int stride = obj.Image.PixelWidth * obj.Image.Format.BitsPerPixel / 8;
    int byteSize = stride * obj.Image.PixelHeight * obj.Image.Format.BitsPerPixel / 8;
    var ary = new byte[byteSize];
    obj.Image.CopyPixels(ary, stride, 0);
 
    DrawCross(stride, ary);
 
    obj.Image.WritePixels(new Int32Rect(0, 0, obj.Image.PixelWidth, obj.Image.PixelHeight), ary, stride, 0);
    obj.Stage = ProcessingStage.Actioned;
}
 
private static void DrawCross(int stride, byte[] ary)
{
    for (var y = 1; y < 47; y++)
    {
        var line1Pos = (y * stride) + (y * 4);
        var line2Pos = (y * stride) + (stride - 4) - (y * 4);
        for (var a = -1; a < 2; a++)
        {
            ary[line1Pos + 4 + (a * 4)] = ary[line2Pos + 4 + (a * 4)] = 255;
            ary[line1Pos + 5 + (a * 4)] = ary[line2Pos + 5 + (a * 4)] = 0;
            ary[line1Pos + 6 + (a * 4)] = ary[line2Pos + 6 + (a * 4)] = 0;
            ary[line1Pos + 7 + (a * 4)] = ary[line2Pos + 7 + (a * 4)] = 0;
        }
    }
}

 

Return to Top


Blackboard Extensibility

Considering how long the Signal processor can take to process the radar data, added to the extra delay in hitting the targets, means some objects may not get processed in time.



This is of course unacceptable in such a system, so it would need to expand, grow with demand. As our controller is simply iterating over a list of known Knowledge Sources, it is a simple matter of adding to that collection. This is demonstrated with the "Add another signal processor" button. each click of this adds extra processing power to each loop of the controller, and after just a few clicks, you will see the images getting identified within just a few iterations.



This represents one of the main selling points of this design pattern.

Extra Knowledge Sources will also bring their own priority attributes, allowing it to slip into the collection at whatever priority is required.

This is also why the Controller is needed, to centralize the decision process and mediate between multiple Knowledge Sources.

 

Return to Top


Download and Try!

This project is available for download and further study in the TechNet Gallery:

http://gallery.technet.microsoft.com/Blackboard-Design-Pattern-13a35a7e

Return to Top


See Also

Links to domain parent articles and related articles in TechNet Wiki.

 

 

Sort by: Published Date | Most Recent | Most Useful
Comments