Sampling-Based Motion Planning Lecture

In the lecture "Sampling-Based Motion Planning: from Intelligent CAD to Crowd Simulation to Protein Folding" here at Clemson, Dr. Nancy Amato of Texas A&M presented improvements to Probabilistic Roadmap Methods (PRM) for solving motion planning problems.

The problems that Dr. Amato described are all set in a n-dimensional Constraint Space (C-Space), where each constraint is one dimension. This could be as simple as a set of Cartesian coordinates or as complicated as bond angles between each carbon in a protein. The motion of the actor within its C-Space is determined by the presence of C-Obstacles, places where the actor cannot move in the C-Space.

PRMs build a set of possible routes through a C-Space by

1. Randomly generating a list of points in the C-Space and discarding invalid points (i.e. those within a certain proximity of an obstacle)
2. Connecting each remaining point to all other points and discarding any invalid connection

PRMs generate the path before the actor even begins moving, making querying paths a matter of looking up results instead of calculating them at the time of the query. Dr. Amato claimed that these methods are probabilistically complete and easily applied to high-dimensional spaces. The major drawback, though, comes from the fact that points are sampled randomly: it is unlikely that the actor will find a path through narrow passages.

The problem, then, is finding ways to sample nodes close to obstacles so that actors may better traverse narrow passages. PRMs that attempt to solve the problem in this way are called Obstacle-Based PRMs (OBPRM). The idea here is to

1. Find a point in an obstacle
2. Select a random direction
3. Find a free point in that direction
4. Determine the the boundary between the obstacle and the free point

The second problem is efficiency of mapping. By the nature of their design, PRMs are relatively easily parallelized at each stage, boosting their efficiency. In the case of moving constraints, PRMs must redo the entire pathfinding process for each distinct configuration of the C-Space. In this case, it is more efficient to repair approximate paths instead of redoing the entire pre-query stage.

In some cases, efficiency can be improved using hybrid human/planner systems in which a human agent traces a path through the space and the planner uses that path data to make decisions. The given example of this system had the human agent trace a path on a haptic device, then the path was passed to the planner. Dr. Amato's group used these systems in CAD designs and deformable object modelling, but she noted that this is only useful when the solution is fairly obvious to humans.

PRMs are also used to aid flocking (coordinated) behavior by helping individual members of the flock to find a path. Dr. Amato's group successfully applied this system to architectural problems.

The most interesting application (thanks to my bias toward biological applications of computing) was protein-folding modelling. While computers have successfully been used to determine the normal state of a protein for some time, they only look at the final state and not how the protein folded into that state. PRMs can model the actual folding process to show how a protein reaches its normal state. The presentation had some of the data from these experiments, and it looked promising, though I can't say I know enough about the results to talk about them in detail.

Overall, PRMs are an interesting concept. Randomness and probability in computing have always interested me because they allow for degrees of flexibility that rigidly logical systems do not provide and make behavior more realistic. These concepts are not necessarily useful in every case, but they provide an alternate way of thinking about how we solve problems that breaks out of the computer science shell.

Tyler Update

February 10th, I took a look at the documentation for Mongoose and easily found a function ("mg_send_response") to directly insert a header into the server's response. I downloaded the latest version of Mongoose and the hello.c example and tested it out on another machine. The hello.c example worked fine as-is but when I tried to add the response header to the code, the page would take at least 30s to load. It turns out I was trying to add a response header after already returning data from the function handler in Mongoose. I needed to set the response header first thing in the function. Once I had the CORS response headers working on localhost, it was time to actually try a cross-domain request with ajax. From a separate machine I tested an ajax call but sadly it still failed. Part of the error message clued me in to the problem. It turns out I was referencing the server by IP only and I needed to prefix the HTTP protocol to the IP in order to get the cross-domain request to work. With cross-domain requests working, I had my co-worker Jeff make the necessary modifications to his Tyler server and then run a test. He connected his macbook to the tile sensors and ran the server while I ran my tyler visualization on a separate machine. The test worked and the results of him walking across the tiles can be observed in the video below:

Grabbing Patterns

The pattern-grabbing code is now functional and can read from the Mongoose server.

The Pattern Grabber

from queue import LifoQueue
def grab_group(graph, rows, cols, x, y):
    q = LifoQueue()
    
    group = Group()

    q.put([x, y])

    while not q.empty():
        tempx, tempy = q.get()
        
        if not group.contains(tempx, tempy, None):
            group.add_point(tempx, tempy, graph[tempy][tempx])
            graph[tempy][tempx] = 0
            
            if tempx > 0 and graph[tempy][tempx - 1] != 0:
                q.put([tempx - 1, tempy])
                
            if tempx < cols and graph[tempy][tempx + 1] != 0:
                q.put([tempx + 1, tempy])

            if tempy > 0 and graph[tempy - 1][tempx] != 0:
                q.put([tempx, tempy - 1])

            if tempy < rows and graph[tempy + 1][tempx] != 0:
                q.put([tempx, tempy + 1])

    group.calculate_center()
    return group

This code makes use of Python's queue.LifoQueu, which is essentially a stack. The function takes an iterable storage data type containing data points, a row size, a column size, and starting coordinates.

Once everything is initialized, the initial points are placed in the queue and the following loop runs until the queue is empty. At each iteration, the next point in the queue is pulled and the group is checked to see if it contains the point.

This check required a small modification to class Point's compare method.

    def compare(self, p):
        '''
        Compares the point passed to self. For coordinate-only comparison, pass
        a point with p.data = None.
        '''
        return (self.coords == p.coords and \
                (self.data == p.data or p.data is None))

Before this change, grab_group() would occasionally grab the same point a second time after the data had been set to zero. This was due to the fact that a previously enqueued data point had since been set to zero, bypassing the checks for a zero data point. It was more useful to give the Point class the option to compare coordinates only than to add a second condition to grab_group().

If the point is not in the group, it is added to the group and that point in the graph is set to zero. Then, each adjacent point is checked for nonzero values. If the adjacent point contains a nonzero data point and is within range of the graph, it is added to the queue.

After all points are added to the group, the center point is calculated as a pair of floating-point values. The group is then returned.

This algorithm is useful despite the potential for checking the same point multiple times because it follows the shape of the data instead of needing information about the shape. For out purposes, it seems fast enough, though it has not been tested using fast, consecutive requests to the Mongoose server.

The Server Request

This is only being documented here because it took some time to work out how to do this properly. Initially, Python's urllib2 module was being used to no effect, and it took some time afterward to work out exactly what needed to be done to retrieve the information.

import httplib
def read_graph_data(f):
    '''Reads pressure data from site f into an array.
    '''
    try:
        #text = open('data.txt')
        conn = httplib.HTTPConnection("127.0.0.1:8080")
        conn.request("GET", "/data")
    except IOError:
        print "Could not open the file."

    text = conn.getresponse()
    #text = text.read()
    conn.close()
    del conn

    #print text
    
    graph = text.split('\n')
    #graph.remove('')
    del text

    for y in xrange(0, len(graph)):
        graph[y] = graph[y].split(' ')
        for x in xrange(0, len(graph[y])):
            graph[y][x] = int(graph[y][x])
    

    return graph

This uses httplib to talk with the server. It opens a connection and requests a specific URI extension. The only response at the page '\data' is the raw data, so no extra formatting work is needed. After this, the formatting and typecasting is straightforward.

The response is split into a list of strings, then each string in the list is split into its own list of strings, and each member of the 2d list is converted into an integer.

Next Steps

Daniel and I were able to get his AJAX calls to the server working today, and he took a video of the result.

I will continue by looking into Python audio libraries and work on a simple program to output audio.

Translating Pressure Data to Audio Output: The Plan

An avenue that I am currently pursuing is taking the pressure data from Tyler by means of my modifications to Tactonic's source code and translating it into audio output. The end-goal here is to use that program to show that a unique signal can be produced from a particular set of pressure data.

Dr. Remy has suggested that I implement this in Python, and the current work on this is being written using Python 2.7.3.

The major problems that this code must solve are:

• Distinguishing between and grabbing pressure groups
• Modulating audio output based on pressure data

As of now, pressure data is being received in a (w * h)n array of integers, where n is the number of pressure sensors and w and h represent the number of sensors in a row or column of sensors, respectively. The test data currently being used is:

The array generated by Tyler is presented as a single string where elements are delimited by either a single space or a newline character. This data allows for a not-quite-rigorous test of group-grabbing code because, despite its appearance, it actually contains three groups.

How is a group defined?

A group, as I mean here, is a contiguous set of nonzero data points adjacent to each other on a Cartesian plane. This definition presents its own challenges. A group can be of any shape so long as each point is adjacent to at least one other point in the group. Any nonzero point that is not adjacent to another point is in its own group. This means that a group can consist of a single point. In the future, more constraints may be added, but for the time being this definition is sufficient for generating code that can handle grabbing groups out of an array.

One example of a decision to make concerning this definition is determining whether or not elements that are "diagonal" will count as adjacent. For the time being, adjacency is limited to points (x - 1, y), (x + 1, y), (x, y - 1), and (x, y + 1).

Implemented in Python, this looks like:

class Group:
    """Group represents a set of points with some relation to one another. In
    addition to the point list, it calculates the coordinates of the center of
    the group."""
    def __init__(self, cx=0.0, cy=0.0):
        self.point_list = []
        self.center = [cx, cy]

The class stores a list of Point objects and a list of coordinates representing the center of the group.

The Point class is simply a storage class that keeps a pair of coordinates and the data stored at those coordinates.

class Point:
    """Point represents one unit of data on a Cartesian plane. In addition to
    coordinate information, it stores the data recorded at the point"""
    def __init__(self, x=0, y=0, d=0):
        self.coords = (x,y) #These do not need to change
        self.data = d      #This is expected to change

What information must a group contain?

Per the definition above, a Group storage type must contain all points within the group and their force data. In addition, groups will contain the coordinates of their center of pressure. This is determined by

CenterX = sum(x * force(x)) / sum(force)
CenterY = sum(y * force(y)) / sum(force)

This is calculated by iterating over the entire group and summing the necessary components at each point. This operation has been rewritten for Python as:

    def calculate_center(self):
        force = 0.0

        for p in self.point_list:
            force += p.data
            self.center[0] += float(p.data) * float(p.coords[0])
            self.center[1] += float(p.data) * float(p.coords[1])

        self.center = [_ / force for _ in self.center]

Looking Forward

The main concern at this point is writing an efficient group-grabbing algorithm. A successful algorithm will be able to pull a group from the array in a single pass with no information about the shape of a group, and it will create no duplicate groups or groups whose points overlap.

As of now, the code pulls information from a text file, but the eventual goal is to be able to read from an array posted online. This functionality will need to be implemented once Tyler is able to interface with the Raspberry Pi.

I have written tentative code for both classes mentioned above. The entirety of the code for those classes as of now is as follows:

class Point:
    """Point represents one unit of data on a Cartesian plane. In addition to
    coordinate information, it stores the data recorded at the point"""
    def __init__(self, x=0, y=0, d=0):
        self.coords = (x,y) #These do not need to change
        self.data = d      #This is expected to change

    def compare(self, p):
        return (self.coords == p.coords and self.data == p.data)

    def print_point(self):
        print '{0:3d} {1:3d} {2:4d}\n'.format(self.coords[0], self.coords[1],
                                            self.data)

class Group:
    """Group represents a set of points with some relation to one another. In
    addition to the point list, it calculates the coordinates of the center of
    the group."""
    def __init__(self, cx=0.0, cy=0.0):
        self.point_list = []
        self.center = [cx, cy]

    def add_point(self, x, y, d):
        self.point_list.append(Point(x, y, d))

    def calculate_center(self):
        force = 0.0

        for p in self.point_list:
            force += p.data
            self.center[0] += float(p.data) * float(p.coords[0])
            self.center[1] += float(p.data) * float(p.coords[1])

        self.center = [_ / force for _ in self.center]
        

    def contains(self, x, y, d):
        p = Point(x, y, d)
        for point in self.point_list:
            if p.compare(point):
                del p
                return True

        del p
        return False

    def print_group_data(self):
        for point in self.point_list:
            point.print_point()
        print "Center {}".format(self.center)

Visualizing Tyler

"Tyler" is a nickname for a set of pressure sensitive tiles we have here at the lab. Each tile contains 576 sensors and is square in shape with 2 foot sides. There are 8 in total and they can be connected in groups to make larger errors for the gathering of data. Currently, data from the tiles can only be read from a device running the appropriate library that just so happens to be Mac OSX dependent. Data is provided as a 2D array of values, each element representing a sensor in the tile(s). Each value is an integer in the range of 0 to 3000 inclusive. We don't yet know the units for these numbers however in the future we may write a calibration program to convert the values to a known metric.

My co-worker and fellow student Jeff Kinnison has been working with Tyler. He has written an application using Mongoose (and the tile driver) to read the tile data and broadcast it as a web service, just like in Claude. I am working on a web application to render the data from this web service in a web page using the HTML5 canvas. Eventually, we will be combining Claude and Tyler to visualize the location of a person's skeleton along with the pressure points of their feet. Currently, I am just trying to render Tyler in 2D. Then I will move to 3 dimensions after that, integration with the skeleton visualization.

I currently have this:

Two tiles where connected horizontally and Jeff placed his foot in the middle. The color key on the right indicates pressure levels. It ranges from low pressure which is turquoise to high pressure which is red. I am currently rendering the sensors as individual cells, note the black outline on the squares that are colored. Black sensors are those which report no pressure (0). Every value above is given a color based on its range in the color key. Each color is given an equal portion of the 0-3000 range to represent. I dynamically determine which color a value falls into so adding a color to the key is as simple as adding it to the list.

The current problem is that the data pictured above did not come directly from Tyler. It was copied and pasted from an HTTP request by the browser. Attempting to make an AJAX call directly from this webpage to Tyler throws a Cross-Domain request. For security reasons, javascript can only make ajax requests (or get requests) to pages on the same domain. Leveraging CORS, it is possible to modify the server's response header to include a value indicating to the web browser (which enforces the regulations) that cross-domain requests are ok. However, Mongoose does not support CORS directly. I worked with Jeff to try and hard code the header value into Mongoose but we were unable to change the results. We will have to look further into this in order to allow Cross-Domain requests. The reason we did not have this issue with Claude and Web-Kamehameha is because Web-Kamehameha had a server-side portion written in C# that was making the web service calls to Claude. Apparently cross-domain requests are allowed by the means with which C# accessed Claude, but not for javascript ajax requests.

Kamehameha Performance

I have tested ajax call performance in the past however now that an end-to-end application for Claude is complete (Web-Kamehameha), it was time to do some more tests. Also, from my last blog post, I was curious to see the results of async vs. sync JavaScript calls as well as various frame rates. I conducted a series of 6 tests by running async and sync tests on 20, 30, and 40 fps. I noticed a strange phenomena while testing kamehameha. As noted earlier in my blog Firefox rendered kamehameha much smoother than Chrome did, however this has recently changed. Firefox now will freeze up after a large number of seconds, around 10. After being frozen for a few seconds, it unfreezes and behaves normally. Chrome's performance has also worsened and has a more consistent rate of dropped frames, albeit still better than Firefox's frame rate when Firefox freezes. However when testing, sometimes Chrome performs smoothly and just fine. Ajax calls execute in about 10-20ms consistently and the rendered video is fine. Other times Chrome lag appears to spike and some calls take up to 300ms. This behavior is typically exhibited immediately on loading the kamehameha page and loading the service calls. Sometimes though it can start smooth or jerky and after a while switch. Normally it would make sense to chalk this up to network performance however Clemson University's wireless internet has a whopping 40mbs up/down and < 20ms ping. It seems unlikely a spike in network traffic couldn't still be handled by the network here but its possible.

Another factor is my setup. I was running Claude on my desktop (specs listed in a previous blogpost) and ran Web-Kamehameha (server) on an old Dell Optiplex 755. I used my netbook (hp dm1) to access the kamehameha front-end (client). Being a netbook, I don't get the best performance when rendering kamehameha at 40+fps however I ran all components on my desktop, which has more than competent hardware for the task at hand, and still experienced spikes of jerky laginess which leads me to believe it is something to do with the browsers themselves. Nonetheless, rather than try to control this behavior, it simply has become part of the results. I'm not posting the results yet but I did record ajax call times as well as the order in which they started and stopped. I will probably analyze the results at some point in the future but for now am moving on to work on an application that combines the abilities of Claude with that of Tyler (see blog here).

Writing to Browser in Mongoose Server: mg_write vs. mg_printf_data

In the last post, it was said that the three pages mongoose generates can take up to 30 seconds to finish working. This was fixed by changing the event handlers so that they used mg_printf_data() instead of mg_write() to put data to the browser. Let's take a look at these functions to see why mg_printf_data() works more quickly than mg_write(). We'll start with mg_write().

mg_write() as it appears in mongoose.c

mg_write() takes a connection, a buffer containing the thing to write, and the length of that buffer, and all it does is call spool().

spool(), when called from mg_write(), writes the buffer to global variable remote_iobuf, a member of the mg_connection passed into mg_write(). It ends up having to reallocate remote_iobuf to hold the buffer's content. This is where the trail of mg_write() ends. Now, let's look at mg_printf_data().

mg_printf_data() as it appears in mongoose.c

This function handles the variable arguments passed to it, then calls mg_vprintf().

mg_vprintf() first deals with formatting in a long string of functions that will not be reproduced here, but end in a call to the stdio.h function vsnprintf(), which works in a similar manner to snprintf(). If the buffer has not been chunked, it calls mg_write(), described above. Otherwise, it calls write_chunk().

write_chunk() determines the length of the chunk then feeds the chunk size, the chunk itself, and newlines into spool(), described above.

The twist ending to this Shyamalan blog post is that no matter how you write to the connection you always go through spool(). This leads me to two possible conclusions:

1. The client was having trouble reading an unchunked connection
2. Voodoo magic

The first makes sense because Firefox and Chrome behaved differently when tested with mg_write(), and so there was some issue with going directly through mg_write(). The second makes sense because the going through mg_printf_data() causes a deeper rabbit hole of functions and more buffer reallocation, and so should be a slower process. This defiance of logic leads me to believe that Cesanta Software employs witch doctors to debug their code.