Personnel Routing Application
Well, it’s the dog days of summer here in Texas and I have been largely doing front-end web site stuff to pay the bills. Nothing of great interest other than CSS and JS wrangling. Pretty boring, in fact
I did get a project in last month that is worth mentioning and from one of my favorite clients. This application involves personnel routing inside an airport, although the application can be extended to any structure for which polygonal outlines of fixed structures are available and real-time user location information is easily accessible.
This is the classic problem of routing a person from point A to point B while taking potential obstacles into account. Fixed obstacles are known in advance and their outlines are available in (long, lat) coordinates.
Although a direct (straight-line) route from A to B is the most desirable, that route might involve a collision with an obstacle. In practical terms, even getting ‘too close’ to an obstacle can be problematic.
The simplest solution is to first check if the line segment from A to B is ‘too close’ to a known obstacle. Since this is a mobile app. and performance is critical, a simple heuristic was chosen, namely to check line segment intersection with the bounding-box of each obstacle. This is a known algorithm and a computationally simple check. If there is no collision, there is an option to check the closest distance between the bounding box and the line segment. If this is inside a prescribed tolerance, then the path may be deemed ‘too close.’
A graph is pre-constructed with nodes being acceptable waypoints through the airport (or other structure). The waypoint graph contains all possible endpoints. Edges are created that contain a list of acceptable moves from a given waypoint to any other waypoint. Euclidean distance is used for edge costs.
The A* algorithm for waypoints can be used to solve the pathfinding problem once the user is routed from point A to a nearby waypoint on the graph. This can be done by selectively searching the graph for the two or three closest nodes and then computing the A* path from each starting waypoint. The lowest-cost path is dynamically drawn onto the user’s phone.
My client did all the app. work and my responsibility was a JS library (suitable for use in Titanium Appcelerator) for the polygon and pathfinding aspects of the problem. The former was taken from the Haxe code from the advanced version of my CompGeo library. The latter was hand-modified from the polygonal library by Michael Baczynski. That code was in Haxe, so I extracted the necessary Haxe classes and hand-coded the JS. This allowed me to make several modifications during the process to fine-tune performance for the application at hand as well as reduce the amount of required code.
In addition to changing the internal A* heuristic, I also modified the path() code to re-initialize the internal dense array (if necessary) on input. This made the library easier to use for my client since multiple waypoint paths are continually computed during the application.
Although this is nothing more than a rehash of game-programming that I’ve done in multiple languages over the last twenty years, it was a very telling project in two respects.
– The large project I did for this same client about a year ago involved Flex mobile. Now, they use Titanium.
AS, JS, BS … as long as the money’s there, I don’t care