Simulation of Robotic Code System

 

Eric Seidler

eric.seidler@wustl.edu

 

Faculty Advisor: Dr. William Smart

wds@cse.wustl.edu

 

 

Abstract

 

Modules are portions of code that run inside the robotic operating system of Lewis the Robot of the Media and Machines Lab at Washington University in Saint Louis.   These modules work together to pass data from hardware sensors to an application that uses the data to complete a given task.  The situation can be represented by a graph structure known as a network; the nodes of the graph represent modules and the edges of the graph represent a possible request for data.  A completed path through the network will contain all of the modules needed to complete a given task and the edges connecting these modules.  Currently, the work for a particular task is not assigned to the modules in any sort of intelligent manner.  The goal of this research project is to find a better way to divide work for a task between the modules, in other words, to find a low-cost path through the network.  To accomplish this task, code was written that automatically generates random networks based on user-defined parameters. Then various path-finding algorithms were developed and tested on these networks.

 

Background

 

This research project deals with optimizing the way in which internal robotic system processes work together to perform a given task or function.  For example, Lewis the Robot is programmed to take a picture of a person’s face.  Before the robot can take the picture, it has to have several key pieces of data such as distance from the subject, lighting conditions, etc.  In order to retrieve these data, the running application has to communicate to modules of code (sub-routines or functions) which in turn communicate to other modules; eventually the chain of communication will directly link a module to a hardware device.  The modules will then transfer the data back to the application, converting and/or abstracting it as necessary at each transition.  An example process can be visualized using the diagram below.

Figure 1: Visualization of Robotic Code Network

Figure 1: Visualization of Robotic Code Network

 

The goal is to improve the way in which tasks are distributed among the modules.  Before this can be done, the situation needs to be represented mathematically.  Since it would be a very complex and time consuming process to write an optimizing program and implement it in the real robotic system, simulation is used to automatically generate random networks according to user-defined parameters.  Once the simulation is assembled, the process of code module optimization can begin.  A global optimization (if possible) would be ideal, but even allocating the tasks in a more optimal way is a great improvement.  Several algorithms for this purpose have been developed and tested.

 

Methodology

 

Initially, networks were created by randomly assigning edges to nodes.  Each node was randomly assigned an abstract cost between 1 and 10 inclusive.  It was soon realized that networks created this way did not accurately represent the situation.  The updated network generation involves randomly assigning inputs and outputs to each node and then connecting corresponding inputs and outputs with an edge (see Figure 2 below).

Figure 2: Edges Formed by Randomly Generated Inputs and Outputs

Figure 2: Edges Formed by Randomly Generated Inputs and Outputs

 

Furthermore, the network was initially represented using an adjacency matrix.  This worked under the initial network generation paradigm, but now there was the concern of keeping track of what type of data was being transferred between the two nodes, or, a label for each edge in the network.  A matrix could not hold both the cost of the nodes and the data types (or labels) of the edges.  A three element edge (see structure below) was created to hold the edge information; networks were then represented by a set of edges and a separate cost vector.

 

[  <node source>    <node destination>    <data type of connection>  ]

 

The idea of a covering path is that for each node, for each type of data type label of the node inputs, only one edge is chosen (see Figure 3 below).

Figure 3: Example of a Covering Path through a Network

Figure 3: Example of a Covering Path through a Network

 

Once the structure of the network and the type of path needed were clear, a process titled iterative recursion was used to find covering paths through the network.  The basic idea is given in the pseudocode below.

 

let current node be the application (source) node

while current node is not a hardware (sink) node

      for each data type of input edge

            find set of edges of this type

            find set of next nodes from these edges

            choose the next node according to some rule

            make recursive call, passing in next node as current

      end

end

 

Several algorithms were finding a covering path through the network were developed and tested on the automatically generated random networks.  Descriptions of the algorithms can be found in the final report which is provided via links at the bottom of the page.

 

 

Results

 

Part of the project involved visually representing the structure of the network and the paths.  The following figures are typical of the types of networks generated and paths being found in the tests that were conducted.

Figure 4: Sample Network Generated

Figure 4: Sample Network Generated

Figure 5: Sample Random Covering Path Generated

Figure 5: Sample Random Covering Path Generated

 

It turns out that network complexity (depth and density) is a function not only of number of nodes, but also of max number of inputs/outputs and the number of data types in the network.

 

For the tests conducted, one characteristic of the network called the test parameter was altered as all the other aspects remained constant.  For each value of the parameter being tested, fifteen or twenty different networks were randomly generated and data (cost of path and time required to find path) were accumulated and eventually averaged for that value of the parameter.  Below is a summary of results.

 

 

An example plot generated by one of the tests is shown below in Figure 6.

Figure 6: Results from Random-Optimal as Compared to other Algorithms

Figure 6: Results from Random-Optimal as Compared to other Algorithms

 

Future work

 

 

 

Documents and Links

Final Report (.doc) (.pdf)
Final Presentation
Project Journal via Google Notebook

ESE Department
ESE Undergraduate Research

Return to the top of the page

Site created by Eric Seidler and last updated on 2 May 2007.