Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Remarks
This Office Action is responsive to Applicants' Amendment filed on June 15, 2022, in which claims 1, 2, 4, 9, 15, and 18 are currently amended. Claims 1-18 are currently pending.
Information Disclosure Statement
The information disclosure statement (IDS) submitted on February 6, 2026 are in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
Response to Arguments
The rejections to claims 1-8 under 35 U.S.C. § 112(b)/(f) are hereby withdrawn, as necessitated by applicant's amendments and remarks made to the rejections.
Applicant’s arguments with respect to rejection of claims 9-18 under 35 U.S.C. 101 based on amendment have been considered, however, are not persuasive.
With respect to Applicant's arguments on p. 9 of the Remarks submitted 2/6/2026 that the 'claims are amended to clarify that a processor comprises executable software", Examiner notes that for claim 9 the amendment still does not necessarily claim the processor, but rather appears to claim a system which is connected to a processor. Examiner asserts that under reasonable interpretation a transitory signal may be connected to a processor, however, claiming such would not make the transitory signal eligible subject matter. Similarly, for claim 9 the claim is still seen as encompassing and being directed towards transitory signals or software. With respect to claim 18 the additional elements are seen as mere instructions to apply the judicial exception using generic computer components.
Applicant’s arguments with respect to rejection of claims 1-18 under 35 U.S.C. 102/103 based on amendment have been considered.
With respect to Applicant's arguments on p. 10 of the Remarks submitted 2/6/2026 that "Alawieh does not disclose a pathfinding task", Examiner respectfully disagrees. Alawieh explicitly states ([p. 26] "we propose a novel approach to predict the routing congestion map for large-scale FPGA designs at the placement stage" [p. 27] "In the FPGA physical design process, placement and routing are the two major stages that map a circuit description into the physical layout") where a routing task is interpreted as synonymous with a pathfinding task.
With respect to Applicant's arguments on p. 10 of the Remarks submitted 2/6/2026 that "Nowhere does Alawieh mention image-to-image mapping that includes mapping that includes mapping a pathfinding problem onto a pathfinding solution represented by another bitmap according to applicant's invention", Examiner respectfully disagrees. First, Examiner notes that the instant claims do not recite "image-to-image mapping that includes mapping that includes mapping a pathfinding problem onto a pathfinding solution represented by another bitmap" but rather "a trainable conditional generative adversarial network (cGAN) operably connected to a processor, the processor comprising executable software to generate an image-to-image mapping for the cGAN, the cGAN trained to interpret a pathfinding task as a graphical bitmap and to map a pathfinding problem onto a pathfinding solution represented by another bitmap of the system" which appears to separate the image-to-image mapping from including mapping a pathfinding problem onto a pathfinding solution. Specifically, the image-to-image mapping in the claim is generated for the cGAN whereas the cGAN is trained to interpret a pathfinding task as a graphical bitmap. The instant claims do not connect the image-to-image mapping with interpreting a pathfinding task as suggested on p. 10 of the Remarks submitted 2/6/2026 and the claim is seen as significantly broader. Second, As acknowledged by Applicant, Alawieh adopts the Pix2Pix CGan model ([p. 28] "CGAN model pix2pix") which is an image to image mapping model by definition and namesake. Alawieh explicitly maps a routing/pathfinding problem to a routing/pathfinding solution ( [p. 27] "In the FPGA physical design process, placement and routing are the two major stages that map a circuit description into the physical layout"). With respect to Applicant's arguments on p. 11 of the Remarks submitted 2/6/2025 that "Alawieh fails to disclose a multiterminal obstacle-avoiding pathfinding system comprising: a trainable conditional generative adversarial network (cGAN) operably connected to a processor, the processor comprising executable software to generate an image-to-image mapping for the cGAN, the cGAN trained to interpret a pathfinding task as a graphical bitmap and to map a pathfinding problem onto a pathfinding solution represented by another bitmap of the system.", Examiner respectfully disagrees. Alawieh discloses ([p. 26 §1] "To address these limitations, we propose a new placement-based routing congestion prediction approach for large-scale FPGA designs. Our proposed approach adopts a new conditional generative adversarial network (CGAN) model, namely pix2pixHD, which performs high-definition (HD) image translations for large images with high resolutions [15]. With HD image translation, our approach can achieve high prediction accuracy for large FPGA designs while relying on well-engineered features that can encode the placement and connectivity information for large-scale designs. Moreover, when substituting the congestion prediction used in state-of-the-art congestion aware placement engine, our prediction scheme results in better placement quality and achieves up to 7% reduction in routed wirelength for the most congested design in ISPD 2016 benchmark").
With respect to Applicant's arguments on p. 11 of the Remarks submitted 2/6/2026 that "Liu fails to disclose a multiterminal obstacle-avoiding pathfinding system that includes "a processor comprising executable software including a loss function that includes a reference path that is compared to a routing path and if the tiles of the routing path exceed or fall short of the reference path the model is penalized, and further wherein the penalties are different for each"" because "Liu mentions a reward as the negative of the total length found by the horizontal and vertical segments", Examiner respectfully disagrees. One of ordinary skill in the art would readily recognize that "The negative length of the RSMT constructed is used as reward" is functionally equivalent to using "the length of the RSMT constructed is used as a penalty". In reinforcement learning a penalty is literally just a negative reward. Liu explicitly states that the motivation of using the negative length is "to encourage the model to find shorter solutions" which is analogous to the instant claims.
With respect to Applicant's arguments on pp. 13-14 of the Remarks submitted 2/6/2026 that "Soboleva does not disclose, teach, or suggest at least a multiterminal obstacle-avoiding pathfinding system including a CGAN that learns per-pixel mapping from an input bitmap to an output bitmap to translate one possible data representation into another", Examiner respectfully disagrees. Soboleva explicitly discloses ([p. 318] "We experimented with two prominent cGAN architectures" [p. 317] "(b) corresponding image; (c) image-input for the generator; (d) image-output of the generator. For (b), (c), (d) image pixels are depicted as squares for illustrative purposes") where FIG. 1 clearly shows a per-pixel mapping from input bitmap (c ) to output bitmap (d) to translate one possible data representation (c ) into another (d).
With respect to Applicant's arguments on p. 14 that "Ma does not disclose, teach, or at least suggest at least a multiterminal obstacle-avoiding pathfinding system including a CGAN that learns per-pixel mapping from an input bitmap to an output bitmap to translate one possible data representation into another", Examiner respectfully disagrees. Ma is explicitly directed towards using a cGAN for pathfinding and FIG. 1 of Ma explicitly demonstrates per-pixel mapping from an input (a) to an output bitmap (c,d) ("Fig. 1: Four stages of the proposed CGAN-RRT* algorithm. (a): The original map. (b): The map(a) added randomly assigned start point and endpoint. (c): The map(b) added predicted possibility distribution of feasible paths generated from the CGAN model. (d): The map(c) added the optimal path generated from the CGAN-RRT* algorithm").
Applicant's arguments directed towards the remaining references are moot as the remaining references are not relied upon to teach the amended limitation.
Claim Rejections - 35 USC § 101
101 Rejection
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 9-18 are rejected under 35 USC § 101 because the claimed invention is directed to non-statutory subject matter.
Regarding claims 9-18 , the claimed invention is directed to non-statutory subject matter. The claims do not fall within at least one of the four categories of patent eligible subject matter because under broadest reasonable interpretation the claims encompass signals-per-se. For example, in claim 9 "operatively connected" does not require the processor to be part of the system and the cGAN can be implemented fully by software which may be stored in transitory computer readable media such as transitory propagating signals.
Similarly, in claim 18 the system and instructions can be comprised entirely by software and/or transitory propagating signals. Therefore, claim 18 is also rejected under 35 USC § 101 because the claimed invention is directed to non-statutory subject matter.
Regarding Claim 18: Claim 18 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Step 1 Analysis: Claim 18 is directed to a system, which may be entirely software or transitory signals, which are not statutory categories.
Step 2A Prong One Analysis: Claim 18 under its broadest reasonable interpretation is a series of mental processes. For example, but for the generic computer components language, the above limitations in the context of this claim encompass machine learning processing, including the following:
a custom loss function having instructions configured to penalize a routing model if a number of tiles, nt, included by the model within a routing path is different from a number of tiles in a reference routing path, nt,ref, wherein penalties for nt exceeding and falling short of nt,ref differ (observation, evaluation, and judgement)
Therefore, claim 18 recites an abstract idea which is a judicial exception.
Step 2A Prong Two Analysis: Claim 18 recites additional elements “a processor comprising executable software including”. However, these additional features are computer components recited at a high-level of generality, such that they amount to no more than mere instructions to apply the judicial exception using a generic computer component. An additional element that merely recites the words “apply it” (or an equivalent) with the judicial exception, or merely includes instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea, does not integrate the judicial exception into a practical application (See MPEP 2106.05(f)). Claim 1 also recites additional elements “performing learning by an autoencoder” which amounts to generally linking the judicial exception to a particular technology or field of use. Therefore, claim 1 is directed to a judicial exception. Therefore, claim 18 is directed to a judicial exception.
Step 2B Analysis: Claim 18 does not include additional elements that are sufficient to amount to significantly more than the judicial exception. As discussed above with respect to the lack of integration of the abstract idea into a practical application, the additional elements recited in claim 18 amount to no more than mere instructions to apply the judicial exception using a generic computer component.
Therefore, when considering the elements separately and in combination, they do not add significantly more to the inventive concept. Accordingly, claim 18 is rejected under 35 U.S.C. § 101.
Claim Rejections - 35 USC § 102
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claims 9, 10, and 11 are rejected under U.S.C. §102(a)(1) as being anticipated by Alawieh (“High-Definition Routing Congestion Prediction for Large-Scale FPGAs”, 2020).
Regarding claim 9, Alawieh teaches A multiterminal obstacle-avoiding pathfinding system comprising:
a trainable conditional generative adversarial network (cGAN) connected to a processor, the processor comprising executable software to generate an image-to-image mapping for the cGAN, the cGAN trained to interpret a pathfinding task as a graphical bitmap and to map a pathfinding problem onto a pathfinding solution represented by another bitmap of the system.([p. 1 §1] "To address these limitations, we propose a new placement-based routing congestion prediction approach for large-scale FPGA designs. Our proposed approach adopts a new conditional generative adversarial network (CGAN) model, namely pix2pixHD, which performs high-definition (HD) image translations for large images with high resolutions [15]. With HD image translation, our approach can achieve high prediction accuracy for large FPGA designs while relying on well-engineered features that can encode the placement and connectivity information for large-scale designs. Moreover, when substituting the congestion prediction used in state-of-the-art congestion aware placement engine, our prediction scheme results in better placement quality and achieves up to 7% reduction in routed wirelength for the most congested design in ISPD 2016 benchmark" pix2pix for FPGA placement interpreted as a pathfinding task represented as a graphical bitmap and to map a pathfinding problem onto a pathfinding solution represented by another bitmap of the system).
Regarding claim 10, Alawieh teaches The multiterminal pathfinding system of claim 9, further comprising a dynamic, synthetically generated or commercially available dataset (example in application) operably connected to the processor.(Alawieh [p. 4 §4.1] "For each benchmark, 200 different random net weighting schemes are obtained, then the corresponding placement results are generated using elfPlace [1]. Then, routing is performed using NCTU-GR [22] to obtain the golden routing congestion maps. As a first step, the feature extraction process described in Section 3.1 is performed to prepare both the input and output images for the learning task" Generated elfPlace data samples using NCTU-GR are interpreted as synthetic routed training samples for training the cGAN.).
Regarding claim 11, Alawieh teaches The multiterminal pathfinding system of claim 10, configured to enable effective parallelization on parallel processing (such as GPU, TPU, NPU or similar) hardware, wherein the system yields over an order of magnitude speedup over traditional approaches with no wirelength overhead.(Alawieh [p. 5 §4.4] "Table 10 compares the runtime for the prediction models to that of running the routing flow (denoted NCTU). The proposed approach can achieve up to 5000× and 51× speedup when using GPU and CPU-only respectively" GPU SIMD cores interpreted as enabling effective parallelization.).
Claim 18 is rejected under U.S.C. §102(a)(1) as being anticipated by Liu (“REST: Constructing Rectilinear Steiner Minimum Tree via Reinforcement Learning”, 2021).
Regarding claim 18, Liu teaches A multiterminal obstacle-avoiding pathfinding system comprising: a custom loss function having instructions configured to penalize a routing model if a number of tiles, nt, included by the model within a routing path is different from a number of tiles in a reference routing path, nt,ref, wherein penalties for nt exceeding and falling short of nt,ref differ ([p. 1135 §1] "In this work, we adopt this new idea to construct RSMT. We proposed Rectilinear Edge Sequence (RES) to represent an RSMT, thus we call our method REST. We also designed an actor-critic neural network model to produce RES, and trained it using reinforcement learning. The negative length of the RSMT constructed is used as reward to encourage the model to find shorter solutions" [p. 1136 §1] "The shortest tree length in L1 norm will be 14 as shown in fig. 1a. However, by introducing extra Steiner points, some edges can be reused, and a rectilinear Steiner minimum tree (RSMT) with even shorter total length can be constructed. Figure 1b illustrates such an RSMT of length 12. The two solid dots are the Steiner points introduced in order to construct the RSMT" See also FIG. 1).
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claims 1, 3, 6, 7, and 8 are rejected under U.S.C. §103 as being unpatentable over the combination of Jain (“Training a Fully Convolutional Neural Network to Route Integrated Circuits”, 2017) and Soboleva (“GAN Path Finder: Preliminary Results”, 2019).
Regarding claim 1, Jain teaches A multiterminal obstacle-avoiding pathfinding system comprising: a bitmap generator comprising a trainable [conditional generative adversarial network (cGAN)] configured to generate a [cGAN] routing architecture solution to connect all terminals([Abstract] "We present a deep, fully convolutional neural network that learns to route a circuit layout ‘net’ with appropriate choice of metal tracks and wire class combinations. Inputs to the network are the encoded layouts containing spatial location of pins to be routed. After 15 fully convolutional stages followed by a score comparator, the network outputs 8 layout layers (corresponding to 4 route layers, 3 via layers and an identity-mapped pin layer) which are then decoded to obtain the routed layouts. We formulate this as a binary segmentation problem on a per-pixel per-layer basis, where the network is trained to correctly classify pixels in each layout layer to be ‘on’ or ‘off ’. To demonstrate learnability of layout design rules, we train the network on a dataset of 50,000 train and 10,000 validation samples that we generate based on certain pre-defined layout constrain").
However, Jain does not explicitly teach and to generate complex, obstacle-avoiding multiterminal net while minimizing wirelength of a routed net.
a bitmap generator comprising a trainable conditional generative adversarial network (cGAN)] configured to generate a cGAN routing architecture solution to connect all the terminals
wherein the cGAN learns per-pixel mapping from an input bitmap to an output bitmap to translate one possible data representation into another.
PNG
media_image1.png
454
1466
media_image1.png
Greyscale
FIG. 1 of Soboleva
Soboleva, in the same field of endeavor, teaches and to generate complex, obstacle-avoiding multiterminal net while minimizing wirelength of a routed net.([p. 316 Abstract] "2D path planning in static environment is a well-known problem and one of the common ways to solve it is to (1) represent the environment as a grid and (2) perform a heuristic search for a path on it. At the same time 2D grid resembles much a digital image, thus an appealing idea comes to being – to treat the problem as an image generation task and to solve it utilizing the recent advances in deep learning. In this work we make an attempt to apply a generative neural network as a path finder and report preliminary results" [p. 316 Abstract] "2D path planning in static environment is a well-known problem and one of the common ways to solve it is to (1) represent the environment as a grid and (2) perform a heuristic search for a path on it. At the same time 2D grid resembles much a digital image, thus an appealing idea comes to being – to treat the problem as an image generation task and to solve it utilizing the recent advances in deep learning. In this work we make an attempt to apply a generative neural network as a path finder and report preliminary results" [p. 317 §3] "Often the length of the path is the cost objective to be minimized" [p. 318 §4] "we intuitively prefer this distance to be maximal between the free pixels and the path pixels" See also FIG. 1)
a bitmap generator comprising a trainable conditional generative adversarial network (cGAN)] configured to generate a cGAN routing architecture solution to connect all the terminals([p. 316 Abstract] "2D path planning in static environment is a well-known problem and one of the common ways to solve it is to (1) represent the environment as a grid and (2) perform a heuristic search for a path on it. At the same time 2D grid resembles much a digital image, thus an appealing idea comes to being – to treat the problem as an image generation task and to solve it utilizing the recent advances in deep learning. In this work we make an attempt to apply a generative neural network as a path finder and report preliminary results" [p. 316 Abstract] "2D path planning in static environment is a well-known problem and one of the common ways to solve it is to (1) represent the environment as a grid and (2) perform a heuristic search for a path on it. At the same time 2D grid resembles much a digital image, thus an appealing idea comes to being – to treat the problem as an image generation task and to solve it utilizing the recent advances in deep learning. In this work we make an attempt to apply a generative neural network as a path finder and report preliminary results" [p. 317 §3] "Often the length of the path is the cost objective to be minimized" [p. 318 §4] "we intuitively prefer this distance to be maximal between the free pixels and the path pixels" See also FIG. 1)
wherein the cGAN learns per-pixel mapping from an input bitmap to an output bitmap to translate one possible data representation into another([p. 318] "We experimented with two prominent cGAN architectures" [p. 317] "(b) corresponding image; (c) image-input for the generator; (d) image-output of the generator. For (b), (c), (d) image pixels are depicted as squares for illustrative purposes" See FIG. 1 where Soboleva explicitly learns a per-pixel mapping from input bitmap (c) to output bitmap (d) to translate one possible data representation (c) into another (d)).
Jain as well as Soboleva are directed towards using neural networks for pathfinding. Therefore, Jain as well as Soboleva are analogous art in the same field of endeavor. It would have been obvious before the effective filing date of the claimed invention to combine the teachings of Jain with the teachings of Soboleva by using the neural network in Jain as the generator model in Soboleva. Soboleva provides as additional motivation for combination ([p. 322] "Observing these results, one can claim that GAN-finder adapts well to the unseen instances with the same obstacle density (success rate exceeds 90%). It is also capable to adapt to the unseen instances of higher obstacle density. Although in this case success rate is notably lower (around 73%), it does not degrade to near zero values, which means that the model has indeed learned some general path finding techniques. One may also notice that GAN-Finder significantly reduces the number of gaps (up to an order of magnitude), compared to baseline. The results achieved on the random dataset are shown in the right column of the Table 1. Again GAN-finder is performing much better than the baseline"). This motivation for combination also applies to the remaining claims which depend on this combination.
Regarding claim 3, the combination of Jain, and Soboleva teaches The multiterminal obstacle-avoiding pathfinding system of claim 1, the trainable cGAN operably connected to a processor comprising executable software configured to generate an image-to-image mapping for the cGAN routing architecture solution.(Jain [p. 5 §5] "Total train time significantly improved from 25 hours (∼7.5 min per epoch) with minibatch of 10 to 16 hours (∼5 min per epoch) with mini-batch of 100, on a Tesla K80 GPU").
Regarding claim 6, the combination of Jain, and Soboleva teaches The multiterminal obstacle-avoiding pathfinding system of claim 1, further comprising a post-processing component configured to merge clustered nets generated by the cGAN.(Soboleva [p. 321] "Fig. 4. From left to right: (1) input, (2) ground truth, (3) baseline pix2pix, (4) pix2pix using cross-entropy, (5) GAN-finder output, (6) GAN-finder output post-processed" [p. 320] "Image Post-processing. To make sure that all obstacles remain at their places we transfer all blocked pixels from the original image to the generated one. Another technique we opt to use is gap-filling. We noticed that often a generated path is missing some segments. We use Bresenham line-drawing algorithm [1] to depict them. If the line segment is drawn across the obstacle, the gap remains" Bridging line gaps interpreted as merging clustered nets via post-processing.).
Regarding claim 7, the combination of Jain, and Soboleva teaches The multiterminal obstacle-avoiding pathfinding system of claim 3, further comprising a parallel processing hardware (such as GPU, TPU, NPU, or similar) operably connected to the processor.(Jain [p. 5 §5] "Total train time significantly improved from 25 hours (∼7.5 min per epoch) with minibatch of 10 to 16 hours (∼5 min per epoch) with mini-batch of 100, on a Tesla K80 GPU").
Regarding claim 8, the combination of Jain, and Soboleva teaches The multiterminal obstacle-avoiding pathfinding routing system of claim 7, further comprising synthetic or commercially available routed training samples for training the cGAN generator, operably connected to the processor of the system.(Soboleva [p. 321 §5] "obstacles of rectangular, diamond and circular shape of random size were put to the map until the random obstacle density in the interval [0.05; 0.5] was reached. The total size of each dataset was 50000, divided into train – 75%, test – 15% and validation – 10%. For each input we built a ground-truth image depicting A∗ path" images with randomly placed shapes interpreted as synthetic training samples.).
Claim 2 is rejected under U.S.C. §103 as being unpatentable over the combination of Jain and Soboleva and in further view of Ichter (“Learning Sampling Distributions for Robot Motion Planning”, 2018) and Ma (“Conditional Generative Adversarial Networks for Optimal Path Planning”, 2020).
Regarding claim 2, the combination of Jain, and Soboleva teaches The multiterminal obstacle-avoiding pathfinding system of claim 1.
However, the combination of Jain, and Soboleva doesn't explicitly teach, wherein the cGAN routing architecture solution is generated according to steps of: executing iteratively the cGAN with inputs from a training dataset to generate a trained model, wherein steps in each iteration are: predicting by a variational autoencoder (VAE) generator a routing path for a set of terminals based on a VAE model,
and distinguishing by a convolutional discriminator between a “true” path from a training dataset and a predicted path from the VAE generator based on a generator model,
updating the VAE model if the convolutional discriminator performed the distinguishing step correctly or updating the generator model if the convolutional discriminator performed the distinguishing step incorrectly,
stopping the executing step when the convolutional discriminator cannot any longer perform the distinguishing step,
and defining a final VAE model as the cGAN routing architecture solution..
Ichter, in the same field of endeavor, teaches The multiterminal obstacle-avoiding pathfinding system of claim 1, wherein the cGAN routing architecture solution is generated according to steps of: executing iteratively the cGAN with inputs from a training dataset to generate a trained model, wherein steps in each iteration are: predicting by a variational autoencoder (VAE) generator a routing path for a set of terminals based on a VAE model, ([p. 7090 §III] "While one iteration of this offline phase is often sufficient, with problems that are expensive to solve and thus expensive to acquire data for, the entire methodology may be performed iteratively. Thus, a partially trained CVAE may generate samples that result in better planning performance, allowing more, high-quality data and subsequently allowing the CVAE to be further trained")
and defining a final VAE model as the cGAN routing architecture solution.([p. 7090 §III] "While one iteration of this offline phase is often sufficient, with problems that are expensive to solve and thus expensive to acquire data for, the entire methodology may be performed iteratively. Thus, a partially trained CVAE may generate samples that result in better planning performance, allowing more, high-quality data and subsequently allowing the CVAE to be further trained").
The combination of Jain and Soboleva as well as Ichter are directed towards conditional neural networks for path finding. Therefore, the combination of Jain and Soboleva as well as Ichter are reasonably pertinent analogous art. It would have been obvious before the effective filing date of the claimed invention to combine the teachings of the combination of Jain and Soboleva with the teachings of Ichter by using and iteratively training a cVAE to generate paths using the RRT algorithm. Ichter provides as additional motivation for combination ([p. 7087 §1] "the proposed methodology is shown to effectively learn representations for the relevant regions of the state space, resulting in an order of magnitude improvement in terms of success rate and convergence to the optimal cost").
However, the combination of Jain, Soboleva, and Ichter do not explicitly teach distinguishing by a convolutional discriminator between a “true” path from a training dataset and a predicted path from the VAE generator based on a generator model.
updating the VAE model if the convolutional discriminator performed the distinguishing step correctly or updating the generator model if the convolutional discriminator performed the distinguishing step incorrectly
stopping the executing step when the convolutional discriminator cannot any longer perform the distinguishing step.
Ma, in the same field of endeavor, teaches and distinguishing by a convolutional discriminator between a “true” path from a training dataset and a predicted path from the VAE generator based on a generator model, ([p. 663] "To make the output indistinguishable from the reality, the generative adversarial networks (GANs) [10] can be applied to this problem. GAN models train a generator to generate outputs that cannot be distinguished from the real images by a synchronously training discriminator which tries to detect fake map" See also FIG. 3(b) which shows convolutional discriminator architecture)
updating the VAE model if the convolutional discriminator performed the distinguishing step correctly or updating the generator model if the convolutional discriminator performed the distinguishing step incorrectly,([p. 667] "As suggested in the original GAN paper [10], we train the generator to maximize log D(o, G(o,z)), instead of minimizing log(1 − D(o, G(o,z))" Minimizing/maximizing the objective interpreted as synonymous with updating the model)
stopping the executing step when the convolutional discriminator cannot any longer perform the distinguishing step, ([p. 665] "GAN models are designed to learn a mapping from random noise z to the output image y. Therefore, the generator of a GAN model is defined as {G : z → y}. It is trained to generate output images that can confuse the discriminator of a GAN" [p. 668] "It takes 75 epochs to train the CGAN model").
The combination of Jain, Soboleva, and Ichter as well as Ma are directed towards using conditional neural networks for path finding. Therefore, the combination of Jain, Soboleva, and Ichter as well as Ma are reasonably pertinent analogous art. It would have been obvious before the effective filing date of the claimed invention to combine the teachings of the combination of Jain, Soboleva, and Ichter with the teachings of Ma by using a convolutional discriminator in the pathfinding neural network system. Ma provides as additional motivation for combination ([p. 2 §1] "The results of the model are promising and show that it can improve the performance of the RRT* algorithm significantly").
Claims 4 and 5 are rejected under U.S.C. §103 as being unpatentable over the combination of Jain and Soboleva and Yang (“An obstacle detoured Routing algorithm based on the Enhanced ACS”, 2004).
Regarding claim 4, the combination of Jain, and Soboleva teaches using the encoded 2D array as a single input to the cGAN, (Soboleva [p. 318] "Types of Images. 3 types of images depicting grids and paths are to be distinguished. First, the image that depicts the grid with only start and goal locations – see Fig. 1c. This is the input. Second, the generated image that is the output of the neural network we are about to construct – see Fig. 1d. Third, the ground truth image that is constructed by rendering the input image with the A* path on it – see Fig. 1a. Ground truth images are extensively used for training, i.e. they serve as the examples of how “good” images look like" See also FIG. 1)
generating by the cGAN an output array with portions that match the input encoded 2D array, wherein values of one or more cells are modified from 0 to 1 making the one or more cells part of a predicted routing path.(Jain [Abstract] "We formulate this as a binary segmentation problem on a per-pixel per-layer basis, where the network is trained to correctly classify pixels in each layout layer to be ‘on’ or ‘off ’").
However, the combination of Jain, and Soboleva doesn't explicitly teach The multiterminal obstacle-avoiding pathfinding system of claim 3, wherein the image-to-image mapping is generated according to the steps of: encoding as a 2D array an input 2D image with input terminals and obstacles, wherein a value of each cell corresponds to its content: ‘t’ for a terminal, ‘o’ for an obstacle, and 0 for an empty cell;.
Yang, in the same field of endeavor, teaches The multiterminal obstacle-avoiding pathfinding system of claim 3, wherein the image-to-image mapping is generated according to the steps of: encoding as a 2D array an input 2D image with input terminals and obstacles, wherein a value of each cell corresponds to its content: ‘t’ for a terminal, ‘o’ for an obstacle, and 0 for an empty cell;([p. 1286] "The ODR problem can be explained via the shadowed obstacles distributed in a rectangular chip area, which is to be routed by a pre:assigned net with two terminals s (source point) and f (target point) as can be seen in Fig.l.To obtain graphically the routable space defined by an undirected graph C=(O", h'), where o"={r,,r> ;..,r,} stands for the obstacles in this routing plane").
The combination of Jain and Soboleva as well as Yang are directed towards using machine learning for pathfinding in IC design. Therefore, the combination of Jain and Soboleva as well as Yang are analogous art in the same field of endeavor. It would have been obvious before the effective filing date of the claimed invention to combine the teachings of the combination of Jain and Soboleva with the teachings of Yang by abstracting the terminal and obstacle in the binary pixel representation of Jain as ‘o’ and ‘t' as is explicitly done in Yang. While this would have been obvious to try for one of ordinary skill in the art before the effective filing date of the claimed invention, it is explicitly reinforced by Yang who provides as additional motivation for combination ([p. 1286 §II] "The ODR problem can be explained via the shadowed obstacles distributed in a rectangular chip area, which is to be routed by a pre-assigned net with two terminals s (source point) and f (target point) as can be seen in Fig.1 to obtain graphically the routable space defined by an undirected graph").
Regarding claim 5, the combination of Jain, Soboleva, and Yang teaches The multiterminal obstacle-avoiding pathfinding system of claim 4, wherein the output array is an output image that comprises the predicted routing path and the input terminals and obstacles.(Soboleva [p. 318] "Types of Images. 3 types of images depicting grids and paths are to be distinguished. First, the image that depicts the grid with only start and goal locations – see Fig. 1c. This is the input. Second, the generated image that is the output of the neural network we are about to construct – see Fig. 1d. Third, the ground truth image that is constructed by rendering the input image with the A* path on it – see Fig. 1a. Ground truth images are extensively used for training, i.e. they serve as the examples of how “good” images look like" See also FIG. 1).
Claims 12 and 13 are rejected under U.S.C. §103 as being unpatentable over the combination of Alawieh and Soboleva and Sun ("Automated Pavement Distress Detection Using Advanced Image Processing Techniques", 2009).
Regarding claim 12, Alawieh teaches The global pathfinding system of claims 9.
However, Alawieh doesn't explicitly teach, further comprising a post-processing component configured to merge clustered nets generated by cGAN.
and a cluster merging instruction set connecting the net clusters, the median filter and cluster merging instruction set operably connected to the system via the processor.
Soboleva, in the same field of endeavor, teaches The global pathfinding system of claims 9, further comprising a post-processing component configured to merge clustered nets generated by cGAN.([p. 321] "Fig. 4. From left to right: (1) input, (2) ground truth, (3) baseline pix2pix, (4) pix2pix using cross-entropy, (5) GAN-finder output, (6) GAN-finder output post-processed" [p. 320] "Image Post-processing. To make sure that all obstacles remain at their places we transfer all blocked pixels from the original image to the generated one. Another technique we opt to use is gap-filling. We noticed that often a generated path is missing some segments. We use Bresenham line-drawing algorithm [1] to depict them. If the line segment is drawn across the obstacle, the gap remains" Bridging line gaps interpreted as merging clustered nets via post-processing.).
Alawieh as well as Soboleva are directed towards using a conditional generative adversarial network for path specific bitmap generation. Therefore, Alawieh as well as Soboleva are reasonably pertinent analogous art. It would have been obvious before the effective filing date of the claimed invention to combine the teachings of Alawieh with the teachings of Soboleva by determining a congestion map for the routing generated by Soboleva. Soboleva provides as additional motivation for combination ([p. 322] "Observing these results, one can claim that GAN-finder adapts well to the unseen instances with the same obstacle density (success rate exceeds 90%). It is also capable to adapt to the unseen instances of higher obstacle density. Although in this case success rate is notably lower (around 73%), it does not degrade to near zero values, which means that the model has indeed learned some general path finding techniques. One may also notice that GAN-Finder significantly reduces the number of gaps (up to an order of magnitude), compared to baseline. The results achieved on the random dataset are shown in the right column of the Table 1. Again GAN-finder is performing much better than the baseline"). This motivation for combination also applies to the remaining claims which depend on this combination.
However, the combination of Alawieh and Soboleva does not explicitly teach and a cluster merging instruction set connecting the net clusters, the median filter and cluster merging instruction set operably connected to the system via the processor.
Sun, in the same field of endeavor, teaches and a cluster merging instruction set connecting the net clusters, the median filter and cluster merging instruction set operably connected to the system via the processor. ([p. 374] "The connectivity analysis of the crack pixels is based on a depth-first searching method. The process consists of two steps: break point determination and gap connection").
The combination of Alawieh and Soboleva as well as Sun are directed towards image processing. Therefore, the combination of Alawieh and Soboleva as well as Sun are reasonably pertinent analogous art. It would have been obvious before the effective filing date of the claimed invention to combine the teachings of the combination of Alawieh and Soboleva with the teachings of Sun by applying a median filter to denoise the generated path bitmap before filling gaps. Sun provides as additional motivation for combination ([p. 373 §1] "Preprocessing is used to improve the quality of the input image in order to facilitate the analysis and interpretation at subsequent stages. Important tasks in preprocessing can include filtering for noise removal, deblurring the image, and the highlighting of specific features").
Regarding claim 13, the combination of Alawieh, Soboleva, and Sun teaches The system of claim 12, wherein the post-processing component is further defined by a median filter for image noise reduction of an invalid net, (Sun [p. 374] "A promising technique would be to use a nonlinear filter which takes the mean and variance of local gray values into account. Other techniques, such as median filtering can be used to reduce the noise while preserving much of the details in the image. To remove the non-uniform background intensity effect we used the following nonlinear filter, as show in (1),").
Claims 14, 15, and 16 are rejected under U.S.C. §103 as being unpatentable over the combination of Alawieh, Soboleva, Sun, and in further view of Chen (“Linear Spectral Clustering Superpixel”, 2017).
Regarding claim 14, the combination of Alawieh, Soboleva, and Sun teaches The system of claim 13.
However, the combination of Alawieh, Soboleva, and Sun doesn't explicitly teach the cluster merging instruction set configured to identify pairs of closest endpoints from two different clusters for all disconnect endpoints based on Manhattan distance, and to merge two clusters, the identified closest terminal endpoints are connected with a maze-routing instruction set.
Chen, in the same field of endeavor, teaches The system of claim 13, the cluster merging instruction set configured to identify pairs of closest endpoints from two different clusters for all disconnect endpoints based on Manhattan distance, and to merge two clusters, the identified closest terminal endpoints are connected with a maze-routing instruction set.([p. 3322] "we empirically merge small isolated superpixels that are less than one fourth of the expected superpixel size to their large neighboring superpixels. When there is more than one candidate for merging, the closest one in the ten-dimensional feature space is chosen empirically. The LSC algorithm is summarized in Algorithm 1" [p. 3321] "the above derivation can be applied to other pixel similarity measurements other than the Euclidean distance. Appendix VI presents the construction of a twenty-dimensional feature space using the L1 norm-based similarity measurement" See also Algorithm 1).
The combination of Alawieh, Soboleva, and Sun as well as Chen are directed towards image processing. Therefore, the combination of Alawieh, Soboleva, and Sun as well as Chen are reasonably pertinent analogous art. It would have been obvious before the effective filing date of the claimed invention to combine the teachings of the combination of Alawieh, Soboleva, and Sun with the teachings of Chen by performing superpixel (cluster) merging based on an L1 (Manhattan) distance. Chen provides as additional motivation for combination ([p. 3317] "as a preprocessing technique for improving the efficiency of computer vision tasks, superpixel segmentation should be of low computational complexity itself").
Regarding claim 15, the combination of Alawieh, Soboleva, Sun, and Chen teaches The system of claim 14, further comprising one or more components to connect all the terminals in the pathfinding solution.(Alawieh [p. 2] "For the connectivity information, it relies on flying lines to encode the connections in the FPGA design as shown in Figure 1(a)").
Regarding claim 16, the combination of Alawieh, Soboleva, Sun, and Chen teaches The system of claim 15, further comprising at least two deep neural networks.(Alawieh [p. 2 §3.2] "Practically, a CGAN is composed of two main components: the generator and the discriminator. The generator G is trained to produce images in the output domain, based on an input image in another domain, that cannot be distinguished from “real” images by an adversarially trained discriminator, D, which is trained to do as well as possible at detecting the generator “fakes”" Generator and discriminator are interpreted as separate neural networks.).
Claim 17 is rejected under U.S.C. §103 as being unpatentable over the combination of Alawieh and Yang.
Regarding claim 17, Alawieh teaches The system of claim 9.
However, Alawieh doesn't explicitly teach further comprising a submodel generator conditioned by an input comprising placed terminals and obstacles.
Yang, in the same field of endeavor, teaches a submodel generator conditioned by an input comprising placed terminals and obstacles.([p. 1286] "The ODR problem can be explained via the shadowed obstacles distributed in a rectangular chip area, which is to be routed by a pre-assigned net with two terminals s (source point) and f (target point) as can be seen in Fig.l.To obtain graphically the routable space defined by an undirected graph C=(O", h'), where o"={r,,r> ;..,r,} stands for the obstacles in this routing plane").
Alawieh as well as Yang are directed towards automated integrated circuit design and analysis. Therefore, Alawieh as well as Yang are reasonably pertinent analogous art. It would have been obvious before the effective filing date of the claimed invention to combine the teachings of Alawieh with the teachings of Yang by applying the congestion analysis of Alawieh to the generated routing of Yang. Yang provides as additional motivation for combination ([p. 1286 §II] "The ODR problem can be explained via the shadowed obstacles distributed in a rectangular chip area, which is to be routed by a pre-assigned net with two terminals s (source point) and f (target point) as can be seen in Fig.1 to obtain graphically the routable space defined by an undirected graph").
Conclusion
THIS ACTION IS MADE FINAL. Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any extension fee pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to SIDNEY VINCENT BOSTWICK whose telephone number is (571)272-4720. The examiner can normally be reached M-F 7:30am-5:00pm EST.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Miranda Huang can be reached on (571)270-7092. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/SIDNEY VINCENT BOSTWICK/Examiner, Art Unit 2124
/MIRANDA M HUANG/Supervisory Patent Examiner, Art Unit 2124
Prosecution Insights