LabVIEW Bug Algorithm

[Alex.T]

Overview

This LabVIEW Project demonstrates how LabVIEW can be used to process the Bug Algorithm, the 'common sense' approach to route planning.

By traveling along a straight line to the target, known as the M Line, the bug algorithm circumambulates around approached obstacles until the straight line can be followed again. This algorithm is inspired by the real world, in how insects attempt to reach a target location.

Figure 1: Bug Algorithm Front Panel.

Description

Using a 3D point cloud, emulating aerial acquisition from a LiDAR, specified start and end locations within space can be navigated between by modelling interactions between the location of our navigator and nearby points in space. This is done by incrementally moving towards our target location and testing the surrounding region if an obstacle is approached. In this instance, an obstacle is treated as any point in the cloud which has a Y value above a set threshold. In real terms, this is akin to treating any point within the cloud that rests above a certain height as an obstacle.

Upon colliding with an obstacle, the group of points within the collision region which comprise our obstacle are avoided by moving around them in an anticlockwise direction, by iteratively testing the angle between the closest lying obstacle and the navigator, and moving perpendicularly from it. This operation is continued until the navigator rests upon the M Line, and can safely move towards the goal location. This project builds upon the Bug Algorithm by incorporating a safety radius; this modifies the Bug Algorithm to ensure a maximum obstacle proximity for the navigator.

This project comes with general purpose VIs used to build and visualise a point cloud with LabVIEW's built in tools. As data from a point cloud is particularly memory intensive, which greatly hinders the rate at which we can draw, the point cloud data is delegated to the graphics card and drawn using LabVIEW's tight integration with OpenGL, for hardware accelerated graphics.

This project is built using LabVIEW's Object Oriented functionality. This shows that although we've only defined the Bug Algorithm in this project, we can build upon the software architecture to support any route planning functionality we'd like, without having to modify the implementation of surrounding code. This has been achieved by defining the generic set of operations and common data that would be necessary for any route planning algorithm within a LabVIEW class, than building the Bug Algorithm into this architecture.

This code is fully documented and ready to include within any existing project based on the acquisition of point cloud data.

Application

This algorithm has been utilised by the University of Manchester for the ICARIS Project (Implementation of Co-operative Autonomous Robotics for Indoor Searching). The ICARIS Project is a final year Electronic and Electrical Engineering (EEE) project which is used to demonstrate collaborative behaviour between semi-autonomous robots in the acquisition of a shared goal. In this application, the team use a UAV to scan an obstacle course using a LiDAR, which is in turn used to generate a 3D topographic map of the environment, comprised of a 3D point cloud. A target object is detected within this cloud, and using the Bug Algorithm, an obstacle-free route for a ground vehicle can be transmitted to allow successful acquisition. Check out the video below to find out more about the ICARIS Project.

Video 1: Team ICARIS Project Video.

Steps to Implement or Execute Code

1. Download the attached LabVIEW Project (Bug Algorithm.zip)
2. Open and execute Bug Algorithm.vi. Every second a randomly generated obstacle course will be used for route planning!
3. Hit the STOP button to end the VI.

Requirements

Software

Created using LabVIEW Student Edition 2013.

Hardware

None.

Additional Images or Video

Because who doesn't like Adventure Time.

[RER]

Woooooah! I just had a look at the project video... amazing work Alex (et al). You shouldve submitted this to the NI Student Design Contest. It wouldve been a strong contender. Out of curiousity, how did you use the myRIO?

Regardless... congratulations man!!

ps. I flippin' love adventure time! It is wasted on kiddies

[Alex.T]

Hey Rich!

Hope you're doing alright! Thanks a lot, I really appreciate that!

We used the myRIO for a lot of performance benchmarking. I've got another VI where we've delegated this algorithm to an FPGA to reason about performance gains (That one is soon to come ), since the Bug Algorithm is highly iterative and fairly computationally intense. I pass the obstacle course into the onboard RAM and push the route through the processing then back up through a DMA FIFO.

We could also quickly take advantage of the wireless connection onboard the device, which allowed us to verify the network efficiency of our system by accumulating large quantities of remote data from the LiDAR and visualise this back at the base station. Our embedded implementation uses XBee modules, which severely capped the scope of our topographic acquisition. We were only able to quantify this through the myRIO!

Adventure Time is the best. All of my friends said it was too weird and nonsensical, so I took it down, but they kept replaying it, so I put it back up!

Anyway, I'd better run off to university. It's my last full day! I really hope you're having fun in Technical Marketing!