Path determination facilitation method

• US 20070094165A1
• Filed: 10/26/2005
• Published: 04/26/2007
• Est. Priority Date: 10/26/2005
• Status: Active Grant

• Current Assignee: Motorola Solutions, Inc.
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Zhang, Jie, Gamota, Daniel, Mok, Swee, Gyorfi, Julius, Toloo, Mansour, Szczech, John
• Granted Patent: US 7,461,035 B2
• Time in Patent Office: Days
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

One facilitates determination of a path that comprises a plurality of specific locations (201). In an optional though preferred embodiment these specific locations comprise locations where a given functional ink will preferably be printed using a continuous printing spray. Also in an optional though preferred embodiment this path will also avoid at least one predetermined area (701) where such a functional ink should not be printed. In a preferred approach this process (100) generally provides for identifying (101) these specific locations and further identifying (102), when applicable, the one or more predetermined areas to be avoided. This process then preferably uses a processor to effect at least one (and preferably both) of using (103) a genetic algorithm to identify a preferred path that includes the plurality of specific locations and using (104) an A* algorithm to process a candidate path to provide a selected path that includes the plurality of specific locations while also avoiding the at least one predetermined area.

Claims

1. A method to facilitate determination of a path that comprises a plurality of specific locations and that avoids at least one predetermined area, comprising:

identifying the plurality of specific locations;

identifying the at least one predetermined area;

in a processor;

using a genetic algorithm to identify a preferred path that includes the plurality of specific locations and that avoids the at least one predetermined area;

processing the preferred path using an A* algorithm to provide a selected path that includes the plurality of specific locations and that avoids the at least one predetermined area.

2. The method of claim 1 wherein using a genetic algorithm to identify a preferred path comprises using a genetic algorithm having at least one gene that comprises at least one polyline, wherein the polyline comprises multiple contiguous path segments.

3. The method of claim 1 wherein using a genetic algorithm to identify a preferred path comprises using a genetic algorithm having a genetic operation comprising reversing a direction of traversing a path segment.

4. The method of claim 1 wherein processing the preferred path using an A* algorithm comprises characterizing the at least one predetermined area to be avoided as a 2 dimensional polygon.

5. The method of claim 4 wherein processing the preferred path using an A* algorithm further comprises determining when a path candidate intersects the 2 dimensional polygon and then modifying that path candidate to provide a modified path candidate that includes some vertices of the 2 dimensional polygon such that the modified path candidate does not intersect the 2 dimensional polygon.

6. The method of claim 1 wherein the plurality of specific locations comprise locations to be sprayed during a printing process and the at least one predetermined area comprises a location that is not to be sprayed during the printing process.

7. The method of claim 6 further comprising:

using the selected path to guide a continuous printing spray.

8. A method to facilitate determination of a path that comprises a plurality of specific locations, comprising:

identifying the plurality of specific locations;

using a processor to process a genetic algorithm to identify a preferred path that includes the plurality of specific locations, wherein the genetic algorithm has at least one gene that comprises at least one polyline, wherein the polyline comprises multiple contiguous path segments.

9. The method of claim 8 wherein using a genetic algorithm to identify a preferred path comprises using a genetic algorithm having a genetic operation comprising reversing a direction of traversing a path segment.

10. The method of claim 9 wherein the path further comprises at least one predetermined area to be avoided and wherein using the processor further comprises using the processor to process the preferred path using an A* algorithm to provide a selected path that includes the plurality of specific locations and that avoids the at least one predetermined area.

11. The method of claim 10 wherein using the processor to process the preferred path using an A* algorithm comprises characterizing the at least one predetermined area to be avoided as a 2 dimensional polygon.

12. The method of claim 11 wherein using the processor to process the preferred path using an A* algorithm further comprises using the processor to determine when a path candidate intersects the 2 dimensional polygon and then modifying that path candidate to provide a modified path candidate that includes some vertices of the 2 dimensional polygon such that the modified path candidate does not intersect the 2 dimensional polygon.

13. The method of claim 8 wherein the plurality of specific locations comprise locations to be sprayed during a printing process.

14. A method to facilitate determination of a path that comprises a plurality of specific locations and that avoids at least one predetermined area, comprising:

identifying the plurality of specific locations;

identifying the at least one predetermined area to be avoided and characterizing the at least one predetermined area to be avoided as a 2 dimensional polygon;

using a processor, processing a path candidate using an A* algorithm to provide a selected path that includes the plurality of specific locations and that avoids the at least one predetermined area as a function, at least in part, of determining when a path candidate intersects the 2 dimensional polygon and then modifying that path candidate to provide a modified path candidate that includes some vertices of the 2 dimensional polygon such that the modified path candidate does not intersect the 2 dimensional polygon.

15. The method of claim 14 wherein using a processor further comprises using the processor to identify the path candidate using a genetic algorithm.

16. The method of claim 15 wherein using a genetic algorithm comprises using a genetic algorithm having at least one gene that comprises at least one polyline, wherein the polyline comprises multiple contiguous path segments.

17. The method of claim 15 wherein using a genetic algorithm comprises using a genetic algorithm having a genetic operation comprising reversing a direction of traversing a path segment.

18. The method of claim 14 wherein the plurality of specific locations comprise locations to be sprayed during a printing process and the at least one predetermined area comprises a location that is not to be sprayed during the printing process.

19. The method of claim 18 further comprising:

using the selected path to guide a continuous printing spray.