**Simulation of Robotic
Code
System**

Eric
Seidler

Faculty
Advisor: Dr. William Smart

**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

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

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

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.

- Random
- Random-Greedy
- Greedy
- Two-Stage
Greedy
- Naive
Optimal
- Random-Optimal

**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 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.

- Greedy produces least expensive
paths
for the time required to find the path
- Greedy and two-stage greedy
produce
paths of nearly identical cost
- Naive optimal doesn’t create
an
optimal path, but does provide a lower bound on the cost of an
optimal
path
- Random-optimal doesn’t take
much
longer to complete as number of nodes
increases
- Random-optimal produces paths that
are
more expensive than paths produced by greedy

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

**Future work**

- Development of more accurate
optimal
algorithm
- Formulation as convex optimization
problem
- Creation of algorithm that is
faster
than an optimal path-finding algorithm but produces better results
than
greedy path-finding algorithm
- Dynamic simulation and real-time
path-finding
- Module
failures
- Local or global compensation for
module failures
- Graphical user interface (GUI) for
simulation
- Implementation in real robotic
operating system

**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