Listing Status
 7763
 , Currently available

 Sale of patent
 Exclusive license with right to enforce
 Exclusive license
 Nonexclusive license
 Region/country license
 Fieldofuse license

 1 Issued Patent  US
Patent for Sale:
M* Path Finding AlgorithmPath Finding Algorithm that is generally faster than Dijkstra/A* with ability to find nextstep without computation of full path.
Overview
The patented MStar 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 nearestneighbor 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.
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 bestfirst algorithm for a given parameter value.
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 bestfirst 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 citysized 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 pathfinding problem is mathematically different from existing algorithms. It relies on a linearalgebraic 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 reusable for the same map, irrespective of the start/destination locations. Dijkstra and A* (and similar) algorithms need to recompute 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, computergame maps and computer networks).
With the MStar 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 startend 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.
With the MStar 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 startend 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, nD?
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 oneway streets, noright 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 4byte floating point representation but rather 2byte or less of data, depending on the necessary level of detail).
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 oneway streets, noright 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 4byte floating point representation but rather 2byte or less of data, depending on the necessary level of detail).
Additional Information
Additional information can be provided upon request. A whitepaper/grey literature can be provided to interested parties.