A clever approach for solving a graph theory problem has led Adelaide software engineering company, Innovation Science Pty Ltd, to be granted a full patent by IP Australia. Granting of the full patent confirms the uniqueness of the approach and plays an important step in protecting the technology for commercialisation around the world. This article offers a glimpse into the ‘eureka moment’ that ultimately led to the patent itself.
What else do you do to pass the time when flying between London and New York? Explore novel ways to solve difficult mathematical problems of course. So with the hum of four 30,000 horsepower engines in the background and a few air pockets to generate some random pen marks on the notebook, a creative approach for solving a graph traversal problem was born.
Granted, most people would probably prefer to read a good novel, but when you’re passionate about your work, work becomes just as fun. And yes, the problem being explored did have a real-life purpose — When someone or something has complete autonomy to traverse any route they please from one point to another, being able to independently determine their exact route has some very distinct advantages. The crux of the problem however, is that as soon as a choice in route is available, the number of route options multiplies. Consider the possibility of doubling-back and the number of route combinations becomes impossibly large.
A series of algorithms and an approach for gathering and storing data were developed which combine to very quickly solve the problem. With only limited computing resources while sitting on an aeroplane, the approach at that stage was purely theoretical, but seemed entirely feasible. Proof of the suite of algorithms required the development of a simulator that could inject millions of simultaneous graph traversals. Verification methods were also developed that could compare algorithm results with truth data. The results were outstanding and the commercial potential was clear.
Core elements of the approach have now become the basis for at least one patent. The first of these has now been awarded in Australia, with full patent protection in a number of key world markets expected to follow in due course.
Graph theory algorithms including those protected by the recently awarded patent have been incorporated in Innovation Science’s Rapid Passenger Tracking software. The Passenger Tracking software is designed to very quickly determine which passengers are of interest to any incident occurring on subway rail systems such as the London Underground, Hong Kong MTR and Seoul Metro. The counter-terrorism and security solution illustrates just one practical application for the novel suite of algorithms.