SEARCH
Tynax ~ Patent Library

Patent for Sale:

M* Path Finding Algorithm    

Path Finding Algorithm that is generally faster than Dijkstra/A* with ability to find next-step without computation of full path.

Overview

The patented M-Star path finding algorithm relies on a matrix approach to quickly determine the path through a map/network from a given starting point to one or more destinations. The algorithm runs at the same speed as a nearest-neighbor algorithm without the danger of becoming 'trapped'. If multiple destinations are possible, it inherently chooses the closest without additional overhead.

Though the initial computational overhead is more involved than Dijkstra/A*, it can be distributed and once completed is reusable for the same map/network, irrespective of start/destination locations.

Primary Application of the Technology

Being a very fast algorithm, it is possible to use it in a topographical form of the Traveling Salesman Problem solver where it replaces the euclidean distance with a more accurate value, representing the actual distance to be traveled.

In computer games, it can provide a convenient method for directing players from one location to another whilst avoiding locations.

In computer science/artificial intelligence, it can be considered a replacement/alternative for the best-first algorithm for a given parameter value.

The Problem Solved by the Technology

By combining the M* algorithm with a Traveling Salesman Problem (TSP) solver, it is possible to determine the best route that involves visits to a large number of locations (such as delivery routes or similar). Since the standard approach is to consider the most direct distance (euclidean distance) between two locations rather than the actual distance being traveled (which considers roads, etc.), the ordering of points is inaccurate. Using the actual distance between two points that reflects the roads between them, a more accurate solution is obtained. Since the number of distances computed for this approach is N^2, even a small difference in computation time leads to a large difference in the total computation time. The M* approach can find a path on a city-sized map between any two points in as little as 1 millisecond, allowing computation of all possible combinations of 100 destinations in as little as 10 seconds (for example, heavily dependent on computational resources).

How the Technology Solves the Problem

The underlying approach to solving the path-finding problem is mathematically different from existing algorithms. It relies on a linear-algebraic definition of the problem and then solves the path/route using established matrix methods (which can be partially solved in parallel which existing path finding solvers cannot). Once the matrix has been established, it is re-usable for the same map, irrespective of the start/destination locations. Dijkstra and A* (and similar) algorithms need to re-compute the path every time either the start or destination changes.

Competitive Advantage

Existing technology often need to iteratively solve the path problem from a starting point to a destination. Though this is beneficial for cases where the map (or network) frequently changes, a lot of effort is wasted when the map remains constant (which is frequently the case for street maps, computer-game maps and computer networks).

With the M-Star approach, the complexities and characteristics of the map is converted into a matrix of values that represent the travel distance, time or similar optimization function for all start-end combinations. This matrix can then be directly interrogated for the path from any given location to any other possible location. This 'stepping' through the locations allows either a full path to be determined or only one (the next) step to be performed, making the approach far faster than any other approach that relies on knowledge of the cost of nearby locations.

Comments on Deal Structure, Potential Terms and Restrictions

Looking for full sale, licensing or similar.

The seller may consider selling these patents individually.

Frequently Asked Questions

Q: Is it possible to run this in 2D, 3D, n-D?
A: Yes, the number of dimensions has no effect on the algorithm. The only additional overhead required is in calculation of the cost parameter to go from one location to its neighbor.

Q: Is it possible to update the matrix with small changes/new information?
A: Once the matrix has been calculated, it cannot be updated with new data. However, for cases where the map may experience changes, a special form of the matrix can be used that allows some amount of dynamic data to be used.

Q: How accurate is the result? Is this the best possible path?
A: The result will depend partially on the definition of the original map. In general, it should be considered approximate/heuristic but will frequently find the best possible path.

Q: What are the issues with determining whether there is a path between two locations?
A: There is a special (proprietary) approach to generating the matrix that can be used for cases where it is possible that not all locations are connected. Using that approach, it is possible to determine whether two locations are connected (by any path) using a single mathematical computation (1 FLOP) without requiring computation of the path at all.

Q:Is the algorithm capable of considering things such as one-way streets, no-right turn intersections and similar?
A: Yes.

Q: How much memory/space/computation is required?
A: In general, the matrix will take a large amount of space. It is of size N^2 (where N is the number of locations). Thus, for a map that contains 100,000 locations, it would require approximately 40GB of space.

Q: How is the approach affected by the number of locations/roads?
A: The matrix being used is of size N^2 and is independent of the number of connections between them.

Q: What other benefits are there?
A: It is possible to run the algorithm using integer math to further accelerate the process and variable resolution is possible too (so distances are not necessarily computed using a 4-byte floating point representation but rather 2-byte or less of data, depending on the necessary level of detail).

Additional Information

Additional information can be provided upon request. A white-paper/grey literature can be provided to interested parties.