Path determination facilitation method

• US 7,461,035 B2
• Filed: 10/26/2005
• Issued: 12/02/2008
• Est. Priority Date: 10/26/2005
• Status: Expired due to Fees

• Current Assignee: Motorola Solutions, Inc.
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Zhang, Jie, Gyorfi, Julius S., Gamota, Daniel R., Mok, Swee M., Szczech, John B., Toloo, Mansour
• Primary Examiner(s): Vincent, David R
• Assistant Examiner(s): Bharadwaj, Kalpana
• Application Number:
  US11/259,482
• Publication Number:
  US 20070094165A1
• Time in Patent Office: 1,133 Days
• Field of Search: 700/104, 701/200, 701/201, 701/209, 706/25, 706/12, 706/14, 706/45, 706/47, 707/3, 707/6
• 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 processor-implemented 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;

in a processor;

using a genetic algorithm to identify a preferred path that includes the plurality of specific locations, the genetic algorithm not altering characteristics of the preferred path and wherein the preferred path is identified by the genetic algorithm without consideration of the at least one predetermined area;

processing the preferred path using an A* algorithm to provide a selected path having a minimum distance around the at least one predetermined area such that the selected path includes the plurality of specific locations and avoids the at least one predetermined area;

wherein the plurality of specific locations comprise locations to be sprayed during a printing process.

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 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 processor-implemented method to facilitate determination of a path that comprises a plurality of specific locations, comprising:

identifying the plurality of specific locations wherein the plurality of specific locations comprise locations to be sprayed during a printing process;

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 fixed length chromosome that includes at least one gene, wherein the at least one gene comprises at least one polyline, wherein the at least one polyline comprises multiple contiguous path segments and wherein the at least one gene includes an indication of a direction of traversal for the at least one polyline of the at least one gene.

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. A processor-implemented 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, identifying a path candidate using a genetic algorithm and without considering the at least one predetermined area to be avoided, processing the 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 and such that a path length of the selected path is minimized;

wherein the plurality of specific locations comprise locations to be sprayed during a printing process.

14. The method of claim 13 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.

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

16. The method of claim 13 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.

17. The method of claim 16 further comprising:

using the selected path to guide a continuous printing spray.