DETAILED ACTION
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 .
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 2023/07/05. The submission is in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
Claim Rejections - 35 USC § 101
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 1–20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Regarding independent claims 1, 8, and 15
Step 1 -- whether the claim falls within any statutory category. See MPEP 2106.03
Claim 1 is drawn to a method claim; claim 8 is drawn to a computer-readable medium claim; claim 15 is drawn to an apparatus claim. Therefore, each of these claims falls under one of the four categories of statutory subject matter (process/method, machine/product/apparatus, manufacture, or composition of matter).
Step 2A Prong 1 – whether the claim recites a judicial exception. See MPEP 2106.04, subsection II.
Regarding independent claim 1, the claim is directed to a method of identifying a path in a graph, the method comprising:
The limitation of "encoding a graph in a neural network, the graph comprising a plurality of nodes connected with one or more edges, the neural network comprising a plurality of neurons with one or more connections, each node encoded in a neuron in the neural network" recites an abstract idea because it describes representing a graph's nodes and edges as a corresponding arrangement of elements — a mapping of information to information that can be performed in the human mind or with pen and paper. This limitation falls within the mental processes grouping of abstract ideas, i.e., concepts performed in the human mind including observation, evaluation, judgment, and opinion. See MPEP § 2106.04(a)(2), subsection III.
The limitation of "causing a forward spike propagation comprising propagation of one or more spikes from a first neuron in the neural network to a second neuron in the neural network" recites an abstract idea because it describes traversing the represented graph outward from a starting element, which is a step of evaluating a data structure that can be performed mentally or with pen and paper. This limitation falls within the mental processes grouping of abstract ideas. See MPEP § 2106.04(a)(2), subsection III.
The limitation of "causing a backward spike propagation comprising propagation of one or more spikes from the second neuron to the first neuron, wherein the backward spike propagation is after the forward spike propagation" recites an abstract idea because it describes traversing the represented graph in the reverse direction, which is likewise a step of evaluating a data structure that can be performed mentally or with pen and paper. This limitation falls within the mental processes grouping of abstract ideas. See MPEP § 2106.04(a)(2), subsection III.
The limitation of "identifying a path in the graph based on the forward spike propagation and the backward spike propagation, wherein the path is between a first node encoded by the first neuron and a second node encoded by the second neuron" recites an abstract idea because it describes selecting a path through the represented graph based on the two traversals, which is an evaluation or judgment based on information. This limitation falls within the mental processes grouping of abstract ideas. See MPEP § 2106.04(a)(2), subsection III.
Accordingly, independent claim 1 recites an abstract idea under Step 2A Prong One because the claim includes limitations falling within the mental processes grouping of abstract ideas. Therefore, the analysis should proceed to Step 2A Prong Two.
Independent claim 8 is a computer-readable non-transitory medium claim reciting limitations similar to claim 1 and is directed towards the abstract idea for similar reasons.
Independent claim 15 is an apparatus claim reciting limitations similar to claim 1 and is directed towards the abstract idea for similar reasons.
Step 2A Prong 2 -- whether the claim as a whole integrates the recited judicial exception into a practical application of the exception or whether the claim is "directed to" the judicial exception. This evaluation is performed by (1) identifying whether there are any additional elements recited in the claim beyond the judicial exception, and (2) evaluating those additional elements individually and in combination to determine whether the claim as a whole integrates the exception into a practical application. See MPEP 2106.04(d).
Regarding independent claim 1, this claim recites the additional element of a "neural network" comprising "a plurality of neurons with one or more connections." This additional element amounts to no more than generally linking the use of the judicial exception to a particular technological environment or field of use (see MPEP § 2106.05(h)), and to mere instructions to apply the abstract idea using a generic neural network recited at a high level of generality that merely serves as a tool on which the abstract idea operates (see MPEP § 2106.05(f)). The claim does not recite a particular improvement to the functioning of a computer or to another technology, because the claim itself does not reflect any specific structural or operational detail of the neural network that would achieve the improvement described in the specification. See MPEP § 2106.05(a) and MPEP § 2106.04(d)(1). The claim also does not recite a particular machine integral to the claim, a transformation of a particular article, or any other meaningful limitation beyond generally applying the abstract idea. See MPEP §§ 2106.05(b), 2106.05(c), and 2106.05(e). Accordingly, the additional element, individually and in combination with the judicial exception, does not integrate the exception into a practical application. Therefore, independent claim 1 is directed to the abstract idea under Step 2A, Prong Two.
Regarding independent claim 8, this claim recites the additional elements of "one or more non-transitory computer-readable media storing instructions" and a "neural network." These additional elements amount to no more than generally linking the use of the judicial exception to a particular technological environment or field of use (see MPEP § 2106.05(h)) and mere instructions to apply the abstract idea using generic computer components recited at a high level of generality (see MPEP § 2106.05(f)), and are rejected under the same rationale as claim 1.
Regarding independent claim 15, this claim recites the additional elements of "a computer processor for executing computer program instructions" and "a non-transitory computer-readable memory storing computer program instructions executable by the computer processor," in addition to the "neural network." These additional elements amount to no more than a generic computer or generic computer components that merely act as a tool on which the abstract idea operates (see MPEP § 2106.05(f)), and generally link the use of the judicial exception to a particular technological environment or field of use (see MPEP § 2106.05(h)), and are rejected under the same rationale as claim 1.
Step 2B -- whether the claim provides an inventive concept. See MPEP 2106.05.
Regarding independent claims 1, 8, and 15, the additional elements — the neural network, the non-transitory computer-readable media, the computer processor, and the computer-readable memory — are recited at a high level of generality and, individually and in combination, do not amount to significantly more than the judicial exception. These elements perform no more than the generic computer functions of storing and executing instructions and providing a computational environment, which do not add a specific limitation beyond the judicial exception that is other than well-understood, routine, and conventional in the field. See MPEP §§ 2106.05(d) and 2106.05(f). Accordingly, claims 1, 8, and 15 do not provide an inventive concept and are not patent eligible.
Regarding dependent claims 2–7, 9–14, and 16–20
Step 2A Prong 1
Regarding claims 2, 9, and 16, each recites that "the graph comprises one or more other paths from the first node to the second node, and the identified path is shorter than the one or more other paths." This limitation recites an abstract idea because it describes comparing path lengths and selecting the shorter — an evaluation or judgment that can be performed in the human mind. This limitation falls within the mental processes grouping of abstract ideas. See MPEP § 2106.04(a)(2), subsection III.
Regarding claims 3, 10, and 17, each recites that "each spiking neuron stores a forward depth value that indicates a distance from the first neuron." This limitation recites an abstract idea because it describes associating a distance value with each element of the represented graph, which is a mathematical relationship — the distance from a reference node — and the storing and manipulation of information through that relationship. This limitation falls within the mathematical concepts grouping of abstract ideas, including mathematical relationships, and additionally within the mental processes grouping. See MPEP § 2106.04(a)(2), subsections I and III.
Regarding claims 4, 11, and 18, each recites that "a forward depth value of the second spiking neuron is determined based on a spike received from the first spiking neuron," the first spiking neuron being "closer to the first neuron than the second spiking neuron." This limitation recites an abstract idea because it describes computing one distance value from another by incrementing along the traversal, which is a mathematical relationship and a calculation. This limitation falls within the mathematical concepts grouping of abstract ideas. See MPEP § 2106.04(a)(2), subsection I.
Regarding claims 5, 12, and 19, each recites that "each spiking neuron stores a backward depth value that is determined based on a spike from the second neuron in the backward spike propagation." This limitation recites an abstract idea because it describes associating a second distance value with each element of the represented graph, measured from the opposite reference node — again a mathematical relationship. This limitation falls within the mathematical concepts grouping of abstract ideas. See MPEP § 2106.04(a)(2), subsection I.
Regarding claims 6, 13, and 20, each recites "determining that a node in the graph is on the path based on a determination that a forward depth value of a spiking neuron encoding the node matches a backward depth value of the spiking neuron encoding the node." This limitation recites an abstract idea because it describes comparing two values for equality and reaching a conclusion based on the comparison, which is an evaluation or judgment that can be performed in the human mind, and a mathematical comparison. This limitation falls within the mental processes and mathematical concepts groupings of abstract ideas. See MPEP § 2106.04(a)(2), subsections I and III.
Step 2A Prong 2
Claims 2–7, 9–14, and 16–20 merely narrow the previously cited abstract idea limitations. For the reasons described above with respect to independent claims 1, 8, and 15, these judicial exceptions are not meaningfully integrated into a practical application. The dependent claims recite no additional elements beyond the neural network, spiking neurons, processor, and memory already addressed with respect to the independent claims, each of which is recited at a high level of generality and merely serves as a tool on which the abstract idea operates. See MPEP §§ 2106.05(f) and 2106.05(h).
Step 2B
For the reasons described above with respect to independent claims 1, 8, and 15, claims 2–7, 9–14, and 16–20 do not recite additional elements that, individually or in combination, amount to significantly more than the judicial exception, and therefore do not provide an inventive concept. See MPEP §§ 2106.05(d) and 2106.05(f). Accordingly, claims 2–7, 9–14, and 16–20 are rejected under 35 U.S.C. § 101.
Claim Rejections - 35 USC § 103
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 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 text of those sections of Title 35, U.S. Code not included in this action can be found in a prior Office action.
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, 2, 7, 8, 9, 14, 15, and 16 are rejected under 35 U.S.C. 103 as being unpatentable over Imam et al. (Imam), U.S. Patent No. US 10,885,425 B2, patented January 5, 2021, in view of Krichmar et al. (Krichmar), Non-Patent Literature, "Flexible Path Planning in a Spiking Model of Replay and Vicarious Trial and Error," From Animals to Animats 16, SAB 202s2, Lecture Notes in Artificial Intelligence vol. 13499, pages 177–189, published 2022.
As to independent Claim 1, the claim recites a computer-implemented method comprising:
encoding a graph in a neural network, the graph comprising a plurality of nodes connected with one or more edges, the neural network comprising a plurality of neurons with one or more connections, each node encoded in a neuron in the neural network;
causing a forward spike propagation comprising propagation of one or more spikes from a first neuron in the neural network to a second neuron in the neural network;
causing a backward spike propagation comprising propagation of one or more spikes from the second neuron to the first neuron, wherein the backward spike propagation is after the forward spike propagation; and
identifying a path in the graph based on the forward spike propagation and the backward spike propagation, wherein the path is between a first node encoded by the first neuron and a second node encoded by the second neuron.
Regarding Claim 1, Imam teaches a computer-implemented method comprising:
Preamble — A computer-implemented method, comprising:
Imam discloses "10. A method comprising: defining a spiking neural network (SNN) to be implemented on a neuromorphic computing device" (Imam, col. 49, lines 57–60), and further discloses that "a neuromorphic computing device 205 may additionally include a processor 225 and system memory 230 to implement logic and one or more components to manage and provide functionality of the neuromorphic computing device 205" (Imam, col. 4, lines 23–27).
Limitation A — encoding a graph in a neural network, the graph comprising a plurality of nodes connected with one or more edges, the neural network comprising a plurality of neurons with one or more connections, each node encoded in a neuron in the neural network
Imam discloses "a portion 400 of an example SNN is illustrated in FIG. 4A that is defined and implemented to include a number of artificial neurons (e.g., 401-406) that are connected according to a particular graph or network topology. Each neuron may correspond to a node in the network topology. Further, at least this portion of the example SNN may be defined and implemented such that each connection between neighboring neurons is bidirectional, such that each connection is implemented with both a synapse (e.g., 407) to support spikes from a first neuron (e.g., 401) to a second neuron (e.g., 402) and a synapse (e.g., 408) to support spikes from the second neuron (e.g., 402) to the first neuron (e.g., 401)" (Imam, col. 13, lines 11–43).
The recited "graph" reads on the particular graph or network topology of Imam; the recited "plurality of nodes connected with one or more edges" reads on the nodes of that topology and the connections between neighboring nodes; the recited "plurality of neurons with one or more connections" reads on artificial neurons 401–406 and synapses 407 and 408 connecting them; and the recited "each node encoded in a neuron in the neural network" reads on the disclosure of Imam that each neuron corresponds to a node in the network topology.
Limitation B — causing a forward spike propagation comprising propagation of one or more spikes from a first neuron in the neural network to a second neuron in the neural network
As an initial matter, the recited "first neuron" and "second neuron" are labels; Claim 1 does not require that the first neuron encode a start node or that the second neuron encode an end node. Under the broadest reasonable interpretation, the recited "first neuron" reads on Neuron 6 of Imam and the recited "second neuron" reads on Neuron 1 of Imam.
Imam discloses "sending a first signal to a first neuron of the plurality of artificial neurons, wherein the first signal is to cause the first neuron to emit one or more first spikes to neighboring neurons in the SNN and cause a wave of spikes to propagate through the SNN" (Imam, col. 49, line 65 – col. 50, line 2). Imam further discloses that "Neuron 6 may be activated (at 505) and in a first time or time step (i.e., t=0) will send a spike message to Neurons 4, 8, and 9 on the outbound synapses respectively connecting Neuron 6 to Neurons 4, 8, and 9" (Imam, col. 16, lines 1–5), and that "Such outward propagation of a spike wave may include not only the spikes sent by Neurons 4, 8, and 9 at t=1, but also Neurons 2 and 7 sending responsive spikes at t=2 to Neurons 1 and 5, Neurons 1 and 5 sending responsive spikes at t=3 to Neuron 3, and Neuron 3 sending a responsive spike at t=4 to Neuron 10" (Imam, col. 16, lines 17–26).
Limitation C, in part — causing a backward spike propagation comprising propagation of one or more spikes from the second neuron to the first neuron
Imam teaches this portion of the limitation. Imam discloses "sending a second signal to a second neuron of the plurality of artificial neurons after the sending of the neuromodulatory signal, wherein the second signal is to cause the second neuron to emit one or more second spikes to neighboring neurons in the SNN, the one or more second spikes are to cause a chain of spikes to propagate to the first neuron on a path" (Imam, col. 50, lines 14–21). Imam further discloses that "Neuron 1 may be activated following training of the SNN causing a spike to be sent from Neuron 1 to Neuron 2 at time t=0" (Imam, col. 18, lines 19–22), and that "propagation of the spike chain originating through the activation 515 of Neuron 1 in this example, ends at Neuron 6" (Imam, col. 18, lines 55–58).
Limitation D, in part — wherein the path is between a first node encoded by the first neuron and a second node encoded by the second neuron
Imam teaches this portion of the limitation. Imam discloses "the path comprises a shortest path in the particular network from a first network node represented by the second neuron to a second network node represented by the first neuron" (Imam, col. 50, lines 26–29). Imam further discloses that "Neuron 1 is selected to designate a corresponding node as the source node and define the problem statement: determining a path in a particular network from a node represented by Neuron 1 and a destination node represented (in this example) by Neuron 6" (Imam, col. 18, lines 1–5). The recited term "between" is not directional.
Imam teaches subject matter related to identifying a path in the graph. Imam discloses determining a shortest path in the network: "the spike chain from source Neuron 1 to Neuron 2 to Neuron 4 to the destination Neuron 6, may be interpreted to represent the shortest path between the source Neuron 1 and the destination Neuron 6" (Imam, col. 18, lines 59–62); "logic to generate path data to describe the path" (Imam, col. 43, lines 40–41); and "determining that the path comprises a shortest path" (Imam, col. 50, lines 26–27). However, Imam does not specify whether the path is determined based on both the forward propagation and the backward propagation, and Imam therefore does not teach identifying a path in the graph based on the forward spike propagation and the backward spike propagation.
Imam further teaches subject matter related to the temporal relationship between the two propagations. Imam discloses sending spikes from Neuron 2 to Neurons 1 and 4 at t=1 (Imam, col. 50, lines 12–15), such that the spikes are sent to both Neuron 1 and Neuron 4 at the same time (t=1), rather than sending the backward propagation to Neuron 1 after the forward propagation to Neuron 4. Imam further discloses the activation of Neuron 1 after the training of the SNN (Imam, col. 18, lines 9–21). However, this does not teach the backward propagation from Neuron 2 to Neuron 1 after the forward propagation, and Imam therefore does not teach wherein the backward spike propagation is after the forward spike propagation.
In the same field of endeavor, Krichmar teaches wherein the backward spike propagation is after the forward spike propagation and identifying a path in the graph based on the forward spike propagation and the backward spike propagation.
Krichmar discloses a spiking neural network in which each node of a graph is encoded in a single neuron: "The spiking wavefront propagation algorithm assumes a grid representation of space. Each grid unit corresponds to a discretized area of physical space, and connections between units represent the ability to travel from one grid location to a neighboring location. Each unit in the grid is represented by a single neuron with spiking dynamics" (Krichmar, page 179, § 2.1).
As to wherein the backward spike propagation is after the forward spike propagation, Krichmar discloses that the forward propagation is performed first and is completed before the backward traversal begins: "the neuron corresponding to the current location (1,1) is induced to spike. This causes an input current to be sent to neighboring neurons, starting a traveling wave of activity across the area covered by the grid. As each neuron spikes, the spike index and the time of spike are logged in a table" (Krichmar, page 181, § 2.3). Krichmar then discloses that the backward traversal is performed thereafter, proceeding in the reverse direction from the goal neuron: "To extract a path from the spike table, a list of neuron IDs is maintained, starting with the goal neuron. The first spike time of the goal neuron is found. Then, the timestamps are decremented until the spiking of a neuron neighboring the goal neuron is found. The process then continues by finding spikes of neurons neighboring the most recent neuron. The process is repeated until the start neuron is found" (Krichmar, page 181, § 2.3). The backward traversal of Krichmar operates on the record of the forward propagation and therefore necessarily occurs after it.
As to identifying a path in the graph based on the forward spike propagation and the backward spike propagation, Krichmar discloses that the identified path is determined from both propagations: the forward traveling wave supplies the logged spike times of the neurons, and the backward traversal from the goal neuron selects, from among those logged spike times, the successive neurons constituting the path, such that "The result is an optimal path between the start and goal" (Krichmar, page 181, § 2.3; see also Krichmar, page 181, Fig. 1B, "Example of using the spike table for extracting a path from (1,1) to (4,4). The extracted path is shown in red font"). Neither propagation alone yields the path in Krichmar: the forward wave alone produces only the table of spike times, and the backward traversal cannot proceed without that table.
Both Imam and Krichmar are analogous art because both are from the same field of endeavor as the claimed invention, namely identifying a path in a graph by propagating spikes through a neural network in which each graph node is encoded in a neuron.
It would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to modify the spiking neural network shortest-path determination of Imam to perform the backward spike propagation after the forward spike propagation, and to identify the path in the graph based on the forward spike propagation and the backward spike propagation, as taught by Krichmar.
The motivation to combine Imam and Krichmar is as recited by Krichmar, which teaches that a timing-based representation "fits better with the idea behind wave propagation than the more commonly used synaptic weight updates" and that performing the backward traversal on the record of the completed forward wave yields "an optimal path between the start and goal" (Krichmar, page 179, § 2.1; page 181, § 2.3).
As to dependent Claim 2, the limitations of Claim 1, from which Claim 2 depends, are rejected under the same rationale set forth above with respect to Claim 1. Claim 2 further recites:
wherein the graph comprises one or more other paths from the first node to the second node, and
the identified path is shorter than the one or more other paths.
Regarding Claim 2, Imam teaches the further limitations as follows:
Limitation A — wherein the graph comprises one or more other paths from the first node to the second node
Imam teaches this limitation.
Imam discloses a network in which a given neuron is reachable from the activated neuron by more than one route. Specifically, Imam discloses that "as shown in FIG. 5C, a single neuron (e.g., Neuron 3) may simultaneously receive two (or more) spikes in a wave of spikes created by activating a single one of the neurons (e.g., Neuron 6)" (Imam, col. 17, lines 4–7). The simultaneous arrival of two spikes at Neuron 3 from a single activated neuron establishes that two distinct routes exist through the modeled network between the node encoded by Neuron 6 and the node encoded by Neuron 3.
Imam further discloses the topology from which the alternative routes between Neuron 6 and Neuron 1 are apparent. Imam discloses that "The block diagram 500b of FIG. 5B illustrates a simplified SNN including ten bi-directionally connected neurons, each neuron representing a respective node in a particular network. Neighboring nodes or connections between nodes in the particular network may be modeled through connections, or synapses, between the artificial neurons modeling the nodes in the SNN" (Imam, col. 15, lines 40–45), and depicts that topology at Imam, sheet 7 of 34, FIG. 5B. In that topology, the node encoded by Neuron 1 and the node encoded by Neuron 6 are connected by more than one route: a first route through Neurons 2 and 4, and a second route through Neurons 3, 5, 7, and 8.
Imam further discloses the propagation of the spike wave along both routes. Imam discloses that the wave from Neuron 6 includes "the spikes sent by Neurons 4, 8, and 9 at t=1, but also Neurons 2 and 7 sending responsive spikes at t=2 to Neurons 1 and 5, Neurons 1 and 5 sending responsive spikes at t=3 to Neuron 3, and Neuron 3 sending a responsive spike at t=4 to Neuron 10" (Imam, col. 16, lines 17–26). The wave thus travels outward from Neuron 6 along the branch through Neuron 4 and Neuron 2 and, in parallel, along the branch through Neuron 8, Neuron 7, and Neuron 5, the two branches converging at Neuron 3 — which is the simultaneous two-spike arrival described at Imam, col. 17, lines 4–7.
Imam further discloses generally that its networks contain plural routes between node pairs and that selecting among them is the problem addressed. Imam discloses that "It may be desirable to determine a path between any two nodes in a network, including those example networks described above. Additionally, it may be desirable to compute a shortest, most efficient, or most preferred path between two nodes. In large complex networks, determining such paths may be a non-trivial and difficult problem. For instance, it may [be] desirable to determine a shortest path between two persons in a social network numbering hundreds of thousands or millions of nodes" (Imam, col. 15, lines 17–26). The recited "one or more other paths from the first node to the second node" read on the alternative routes among which Imam selects.
Limitation B — the identified path is shorter than the one or more other paths
Imam teaches this limitation.
Imam discloses "determining that the path comprises a shortest path in the particular network from a first network node represented by the second neuron to a second network node represented by the first neuron" (Imam, col. 50, lines 26–29). A path determined to be "a shortest path" in the network is necessarily shorter than the other paths between the same two nodes.
Imam further discloses, with respect to the identified path itself, that "the spike chain from source Neuron 1 to Neuron 2 to Neuron 4 to the destination Neuron 6, may be interpreted to represent the shortest path between the source Neuron 1 and the destination Neuron 6" (Imam, col. 18, lines 59–62). The identified path (Neuron 1 → Neuron 2 → Neuron 4 → Neuron 6) traverses three connections, while the alternative route through Neurons 3, 5, 7, and 8 traverses five; the identified path is therefore shorter than the one or more other paths.
Imam further discloses that "Building upon the principles introduced in the example shown in FIGS. 4A-4B, a shortest or most efficient path may be determined between any two nodes in a network topology utilizing the principles and STDP learning rules introduced in the example of FIGS. 4A-4B as applied to an SNN modeling the network topology" (Imam, col. 14, lines 51–55).
Imam further discloses that "FIGS. 5A-5G show simplified block diagrams 500a-g illustrating an example utilizing STDP in an example SNN to determine a shortest path between any two nodes in a network modeled by the SNN" (Imam, col. 15, lines 32–35), and that "To solve for a shortest path between any two nodes in the particular network, the SNN may be configured to model STDP similar to the configuration introduced above in FIG. 4A" (Imam, col. 15, lines 46–49).
Imam further discloses the mechanism by which the shorter path, rather than a longer one, is the path identified. Imam discloses that "With the synaptic weights of the bi-directionally connected neurons strengthened in a direction opposite to the direction of the spike wave generated by one of the neurons (e.g., Neuron 6) according to an STDP rule defined for the SNN, the adjusted synaptic weights may be leveraged to determine a shortest path from any one of the neurons to the neuron (e.g., Neuron 6), from which the spike wave originated" (Imam, col. 17, lines 20–30). Imam further discloses that a neuron "is not allowed to send an outbound spike and/or process an incoming spike for some period (i.e., the refractory period) following the sending of its last outbound spike" (Imam, col. 15, lines 57–61), and that enforcing a refractory period "may enhance the usefulness of STDP, such as in network path finding applications, including those described herein" (Imam, col. 5, lines 3–6). Imam further discloses "exclusive selection logic 250, which may be used to perform conflict resolution in connection with STDP, such that when two spikes are received at the same time (e.g., within the same time step of the SNN)" only one is selected (Imam, col. 5, lines 7–11; see also col. 17, lines 8–19: "the neuron selects (e.g., arbitrarily) only one of the simultaneously received spike messages ... resulting in the weight of only one of the incoming synaptic paths being adjusted according to STDP"). By these mechanisms, only the synapse carrying the earliest-arriving spike — which travels the shortest route — is strengthened, so that the subsequently generated spike chain follows the shortest path rather than a longer one.
As to dependent Claim 7, the limitations of Claim 1, from which Claim 7 depends, are rejected under the same rationale set forth above with respect to Claim 1. Claim 7 further recites:
identifying one or more neurons that spike in the forward spike propagation and in the backward spike propagation; and
identifying one or more nodes in the graph that are encoded by the one or more neurons,
wherein the path comprises connections among the first node, the one or more nodes, and the second node.
Regarding Claim 7, Imam teaches:
Limitation A — identifying one or more neurons that spike in the forward spike propagation and in the backward spike propagation
Imam teaches this limitation.
As set forth in the rejection of Claim 1, the recited "first neuron" reads on Neuron 6 of Imam, the recited "second neuron" reads on Neuron 1 of Imam, the recited "forward spike propagation" reads on the wave of spikes of Imam, and the recited "backward spike propagation" reads on the chain of spikes of Imam. The recited "one or more neurons" read on Neuron 4 and Neuron 2 of Imam.
Neuron 4 and Neuron 2 spike in the wave of spikes. Imam discloses that "the spike sent from Neuron 6 to Neurons 4, 8, and 9 at t=0, will cause Neurons 4, 8, and 9 to send spikes on all of their outbound synapses. In this example, Neurons 4 and 8 will send spikes along to Neurons 2 and 7 respectively at time t=1" (Imam, col. 16, lines 6–10), and that the outward propagation includes "Neurons 2 and 7 sending responsive spikes at t=2 to Neurons 1 and 5" (Imam, col. 16, lines 17–26).
Neuron 4 and Neuron 2 also spike in the chain of spikes. Imam discloses that "reception of the spike from Neuron 1 causes Neuron 2 to also fire, sending spikes to its neighboring neurons. For instance, at time t=1, Neuron 2 may send spikes to Neurons 1 and 4 … to cause a postsynaptic spike (e.g., by Neuron 4 at t=2). In this example, Neuron 4 sends spikes at time t=2 to Neurons 2 and 6" (Imam, col. 18, lines 35–46).
Imam further discloses that every neuron reached by the chain necessarily also spiked in the wave, because the wave reaches all connected neurons: "The activation of the first neuron can cause the first neuron to send spikes to all of its immediate neighboring neurons, which will in turn cause further spikes to be sent, forming a spike wave that may propagate until all neurons connected in the SNN … have received a spike" (Imam, col. 35, lines 34–38).
Imam teaches identifying those neurons. Imam discloses that "Monitoring and/or reporting logic may be provided to identify the order and source of spikes sent in this chain of spikes. For instance, routers of a neuromorphic computing device may be monitored to identify traffic between (or within) one or more neuromorphic cores that identifies the spike messages that result from activating Neuron 1 following training" (Imam, col. 18, lines 62–67). Imam further discloses that "In connection with the activating the source neuron, the path manager 615 … may communicate 640 with a traffic monitor 620 to initiate monitoring 634 of traffic on the neuromorphic computing device 205 associated with the activation of the source neuron. The monitored traffic may correspond to spike messages in the spike chain sent between neuromorphic cores for the neurons implemented on the neuromorphic computing device 205" (Imam, col. 21, lines 19–26).
Imam further discloses that the monitoring spans both propagations. Imam discloses that "A controller utility (internal or external to the neuromorphic computing device) may be associated with the monitoring of traffic in the SNN, such that the monitoring is orchestrated in connection with the training of the SNN and activation of the designated source neuron (as well as the activation of the designated destination neuron during training)" (Imam, col. 19, lines 1–8). The training of the SNN is the wave of spikes initiated by activating the destination neuron (Imam, col. 17, lines 20–23: "the example of FIG. 5C may correspond to a training phase"), and the activation of the designated source neuron is the chain of spikes. The monitoring of Imam therefore observes the neurons spiking in the wave of spikes and the neurons spiking in the chain of spikes, and identifies Neuron 4 and Neuron 2, which spike in both.
Limitation B — identifying one or more nodes in the graph that are encoded by the one or more neurons
Imam teaches this limitation.
Imam discloses that each neuron encodes a node — "each artificial neuron in the SNN models a respective one of a plurality of nodes within the particular network topology" (Imam, col. 50, lines 36–40); "Each neuron may correspond to a node in the network topology" (Imam, col. 13, lines 19–20) — and that the identified spiking neurons are used to identify the corresponding nodes.
Imam discloses "the identification of the path based on a spike chain propagated across the SNN from Neuron 1 to Neuron 6 based on the training" (Imam, col. 19, lines 15–21). Imam further discloses that "This spike chain may also be observed or recorded and used to represent a path in a network topology from the node represented by Neuron 7 to [the node represented by Neuron 6]" (Imam, col. 19, lines 28–31). Imam further discloses that "A corresponding physical location may be determined for each neuron sending a spike in the spike chain to determine a shortest path to the physical destination environment (e.g., by navigating, in order, through each one of the locations corresponding to the neurons (e.g., Neurons A-F) in the spike chain)" (Imam, col. 22, lines 47–54).
Imam further discloses that the path manager generates data identifying the nodes so determined: "the traffic monitor 620 may report 640 the observed traffic on the neuromorphic computing device to the path manager 615. The path manager 615 … may generate network path data corresponding to the monitored traffic that represents a shortest path in the particular network from the source node to the destination node" (Imam, col. 21, lines 27–33). Imam further discloses "logic to generate path data to describe the path" (Imam, col. 43, lines 40–41).
Limitation C — wherein the path comprises connections among the first node, the one or more nodes, and the second node
Imam teaches this limitation.
Imam discloses that the identified path is the ordered sequence running through the neurons that spike in both propagations: "the spike chain from source Neuron 1 to Neuron 2 to Neuron 4 to the destination Neuron 6, may be interpreted to represent the shortest path between the source Neuron 1 and the destination Neuron 6" (Imam, col. 18, lines 59–62). The path of Imam thus runs from the node encoded by Neuron 1 (the recited second node), through the nodes encoded by Neuron 2 and Neuron 4 (the recited one or more nodes), to the node encoded by Neuron 6 (the recited first node).
Imam further discloses that the path comprises the connections joining those nodes. Imam discloses that the chain of spikes propagates "to the first neuron on a path comprising a subset of the portion of artificial synapses" (Imam, col. 50, lines 20–21), and that the SNN is "used to model a path between points in a network (through a spike chain generated through activation of a source neuron (e.g., 652) on synapses (e.g., 657-661) strengthened through previous training of the SNN)" (Imam, col. 22, lines 1–5). Imam further discloses that "Neighboring nodes or connections between nodes in the particular network may be modeled through connections, or synapses, between the artificial neurons modeling the nodes in the SNN" (Imam, col. 15, lines 43–45), such that the synapses carrying the chain of spikes correspond to the connections among the recited nodes.
Claim 8 recites a non-transitory computer-readable medium storing instructions that, when executed, perform operations corresponding in scope to the limitations of Claim 1. Claim 8 is rejected based on the same rationale as set forth above with respect to Claim 1.
Claim 9 recites limitations that correspond in scope to the limitations of Claim 2. Claim 9 is rejected based on the same rationale as set forth above with respect to Claim 2.
Claim 14 recites limitations that correspond in scope to the limitations of Claim 7. Claim 14 is rejected based on the same rationale as set forth above with respect to Claim 7.
Claim 15 recites an apparatus comprising a computer processor and a non-transitory computer-readable memory storing computer program instructions executable by the computer processor to perform operations corresponding in scope to the limitations of Claim 1. Claim 15 is rejected based on the same rationale as set forth above with respect to Claim 1.
Claim 16 recites limitations that correspond in scope to the limitations of Claim 2. Claim 16 is rejected based on the same rationale as set forth above with respect to Claim 2.
Claims 3, 4, 10, 11, 17, and 18 are rejected under 35 U.S.C. 103 as being unpatentable over Imam in view of Krichmar, further in view of Aimone et al. (Aimone), Non-Patent Literature, "Provable Advantages for Graph Algorithms in Spiking Neural Networks," SPAA '21: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, pages 35–47, published July 6–8, 2021.
As to dependent Claim 3, the limitations of Claim 1, from which Claim 3 depends, are taught by Imam under the same rationale set forth above with respect to Claim 1. Claim 3 further recites:
the forward spike propagation has a plurality of spiking neurons that comprises the first neuron, the second neuron, and one or more other neurons between the first neuron and the second neuron, and
each spiking neuron stores a forward depth value that indicates a distance from the first neuron.
Regarding Claim 3, Imam teaches:
Limitation A — the forward spike propagation has a plurality of spiking neurons that comprises the first neuron, the second neuron, and one or more other neurons between the first neuron and the second neuron
Imam teaches this limitation.
As set forth in the rejection of Claim 1, the recited "first neuron" reads on Neuron 6 of Imam and the recited "second neuron" reads on Neuron 1 of Imam.
Imam discloses that the spike wave causes a plurality of neurons to spike. Specifically, Imam discloses that "Neuron 6 may be activated (at 505) and in a first time or time step (i.e., t=0) will send a spike message to Neurons 4, 8, and 9" (Imam, col. 16, lines 1–5); that "the spike sent from Neuron 6 to Neurons 4, 8, and 9 at t=0, will cause Neurons 4, 8, and 9 to send spikes on all of their outbound synapses. In this example, Neurons 4 and 8 will send spikes along to Neurons 2 and 7 respectively at time t=1" (Imam, col. 16, lines 6–10); and that "Such outward propagation of a spike wave may include not only the spikes sent by Neurons 4, 8, and 9 at t=1, but also Neurons 2 and 7 sending responsive spikes at t=2 to Neurons 1 and 5, Neurons 1 and 5 sending responsive spikes at t=3 to Neuron 3, and Neuron 3 sending a responsive spike at t=4 to Neuron 10" (Imam, col. 16, lines 17–26).
The plurality of spiking neurons of the spike wave of Imam thus comprises Neuron 6 (the recited first neuron), Neuron 1 (the recited second neuron), and Neurons 4, 8, 9, 2, 7, 5, 3, and 10. Among these, Neuron 4 and Neuron 2 lie between Neuron 6 and Neuron 1 on the path along which the wave travels from Neuron 6 to Neuron 1, reading on the recited "one or more other neurons between the first neuron and the second neuron." Imam confirms that Neuron 4 and Neuron 2 lie between Neuron 6 and Neuron 1 by disclosing that "the spike chain from source Neuron 1 to Neuron 2 to Neuron 4 to the destination Neuron 6 ... may be interpreted to represent the shortest path between the source Neuron 1 and the destination Neuron 6" (Imam, col. 18, lines 59–62). Imam further depicts the spike wave and the neurons it traverses at Imam, sheet 8 of 34, FIG. 5C.
However, Imam does not teach each spiking neuron stores a forward depth value that indicates a distance from the first neuron. The state variables stored at the neurons of Imam are the membrane potential and the dendritic currents (Imam, col. 10, lines 45–47), and the values adjusted by the spike wave of Imam are the weights of the synapses, not values held at the neurons (Imam, col. 16, lines 41–45: "FIG. 5D illustrates a representation of the individual synapses in the example SNN, which have had their weights strengthened according to STDP based on the spike wave illustrated in FIG. 5C"). Imam does not disclose storing at each spiking neuron a value that indicates that neuron's distance from the activated neuron.
In the same field of endeavor, Aimone teaches each spiking neuron stores a forward depth value that indicates a distance from the first neuron.
As to the storing of a value at each spiking neuron, Aimone discloses under the heading "Neuromorphic memory" that "Our algorithms must store information at graph nodes. We may use neurons with no leakage or self-loops to preserve state (see Figure 1)" (Aimone, p. 5, left col., ¶ "Neuromorphic memory"). Aimone further discloses that each node retains a stored value across the propagation: "Each node needs to remember a neighbor that sends the first spike. Each node has a unique ID from 0 to n − 1. When node v receives its first spike from node u, it sends a binary encoding of its ID to its neighbors, and 'latches' (remembers) the ID u" (Aimone, p. 6, right col., § 3, ¶ 1).
As to the stored value being a forward depth value that indicates a distance from the neuron at which the propagation originated, Aimone discloses that "Because synapse delays are proportional to corresponding graph-edge lengths, a spike that arrives at a node v at time t corresponds to a path from source vₛ to node v of length t. Thus the spike timing mimics the priority queue in Dijkstra's algorithm" (Aimone, p. 6, right col., § 3, ¶ 1).
Aimone further discloses expressly encoding and storing such a value at each node in the form of a time-to-live: "instead of a node u sending a single spike to a neighbor v, it sends ⌈log k⌉ spikes that encode a time to live (TTL). At the start, the node corresponding to vₛ sends ⌈log k⌉ spikes to each neighbor encoding the value k − 1. If a node v receives a spike message encoding the value k′ at time t, then there is a path from source vₛ to node v of length t that traverses k − k′ edges" (Aimone, p. 6, right col., § 4.1, ¶ 1). Aimone further discloses that the node holds and operates on that value: "the circuit computes the largest TTL k′ from any of the incoming spikes, and sends a spike encoding k′ − 1 to all its neighbors if k′ ≥ 1" (Aimone, p. 6, right col., § 4.1, ¶ 2).
The value k′ stored at each node of Aimone indicates that node's distance from the source node, because the number of edges traversed from the source is k − k′ (Aimone, p. 6, right col., § 4.1, ¶ 1). The value k′ therefore reads on the recited "forward depth value that indicates a distance from the first neuron." Aimone further discloses that the propagation begins at a single designated neuron and travels outward: "At the start, the neuron corresponding to the source vertex vₛ sends a spike to each neighbor. Every other neuron propagates only the first incoming spike it receives (ties are fine) to all its outgoing neighbors" (Aimone, p. 6, left col., § 3, ¶ 2), which corresponds to the spike wave of Imam originating at Neuron 6.
Imam and Aimone are analogous to the claimed invention as both are from the same field of endeavor of determining a shortest path through a graph by propagating spikes through a spiking neural network implemented on neuromorphic hardware. Imam is directed to "utilizing STDP in an example SNN to determine a shortest path between any two nodes in a network modeled by the SNN" (Imam, col. 15, lines 32–35), where "each artificial neuron in the SNN models a respective one of a plurality of nodes within the particular network topology" (Imam, col. 50, lines 36–40). Aimone is directed to "neuromorphic graph algorithms, focusing on shortest path problems" executed in "networks consisting of spiking artificial neurons" (Aimone, p. 1, Abstract), and expressly identifies Intel's Loihi neuromorphic processor as a target platform for such algorithms (Aimone, p. 1, right col., § 1, ¶ 1: "there are increasingly large-scale efforts, including industrial efforts from IBM (TrueNorth, [28]) and Intel (Loihi, [10])").
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to combine the spiking-neural-network shortest-path determination of Imam with the storage at each spiking neuron of a forward depth value indicating distance from the activated neuron, as taught by Aimone, such that each neuron of the spike wave of Imam stores a value indicating its distance from Neuron 6.
The motivation to combine Imam and Aimone is as recited by Aimone, which teaches that storing distance state at graph nodes in a spiking neural network yields "energy consumption orders of magnitude lower than conventional high-performance computing systems" and a proven "polynomial-factor advantage" over conventional shortest-path computation (Aimone, p. 1, Abstract).
As to dependent Claim 4, the limitations of Claim 1 and Claim 3, from which Claim 4 depends, are taught by the combination of Imam and Aimone under the same rationale set forth above with respect to Claim 1 and Claim 3. Claim 4 further recites:
a path of the forward spike propagation comprises a first spiking neuron and a second spiking neuron that are between the first neuron and the second neuron,
the first spiking neuron is closer to the first neuron than the second spiking neuron in the path of the forward spike propagation, and
a forward depth value of the second spiking neuron is determined based on a spike received from the first spiking neuron.
Regarding Claim 4, Imam teaches:
Limitation A — a path of the forward spike propagation comprises a first spiking neuron and a second spiking neuron that are between the first neuron and the second neuron
Imam teaches this limitation.
As set forth in the rejection of Claim 1, the recited "first neuron" reads on Neuron 6 of Imam and the recited "second neuron" reads on Neuron 1 of Imam. The recited "first spiking neuron" reads on Neuron 4 of Imam and the recited "second spiking neuron" reads on Neuron 2 of Imam.
Imam discloses the path along which the spike wave travels from Neuron 6 to Neuron 1. Specifically, Imam discloses that "Neuron 6 may be activated (at 505) and in a first time or time step (i.e., t=0) will send a spike message to Neurons 4, 8, and 9 on the outbound synapses respectively connecting Neuron 6 to Neurons 4, 8, and 9" (Imam, col. 16, lines 1–5); that "the spike sent from Neuron 6 to Neurons 4, 8, and 9 at t=0, will cause Neurons 4, 8, and 9 to send spikes on all of their outbound synapses. In this example, Neurons 4 and 8 will send spikes along to Neurons 2 and 7 respectively at time t=1" (Imam, col. 16, lines 6–10); and that the outward propagation includes "Neurons 2 and 7 sending responsive spikes at t=2 to Neurons 1 and 5" (Imam, col. 16, lines 17–26).
Imam further discloses the sequence expressly in a single passage: "For instance, as shown in FIG. 5C, Neuron 2, may receive a spike from Neuron 4 at time t=1, and Neuron 2 may, in turn, send a spike to propagate the spike wave to Neuron 1 ... at time t=2" (Imam, col. 16, lines 48–53).
The path of the spike wave of Imam is therefore Neuron 6 → Neuron 4 → Neuron 2 → Neuron 1, and Neuron 4 and Neuron 2 both lie between Neuron 6 and Neuron 1 on that path, reading on the recited "a first spiking neuron and a second spiking neuron that are between the first neuron and the second neuron." Imam confirms that Neuron 4 and Neuron 2 lie between Neuron 6 and Neuron 1 by disclosing that "the spike chain from source Neuron 1 to Neuron 2 to Neuron 4 to the destination Neuron 6 ... may be interpreted to represent the shortest path between the source Neuron 1 and the destination Neuron 6" (Imam, col. 18, lines 59–62). Imam further depicts this path at Imam, sheet 8 of 34, FIG. 5C.
Limitation B — the first spiking neuron is closer to the first neuron than the second spiking neuron in the path of the forward spike propagation
Imam teaches this limitation.
Imam discloses that Neuron 4 is directly connected to Neuron 6 and receives Neuron 6's spike in the first time step: "Neuron 6 may be activated (at 505) and in a first time or time step (i.e., t=0) will send a spike message to Neurons 4, 8, and 9 on the outbound synapses respectively connecting Neuron 6 to Neurons 4, 8, and 9" (Imam, col. 16, lines 1–5).
Imam further discloses that Neuron 2 does not receive Neuron 6's spike directly, but receives it only after it has been relayed through Neuron 4 in the following time step: "Neurons 4 and 8 will send spikes along to Neurons 2 and 7 respectively at time t=1" (Imam, col. 16, lines 6–10), and "Neuron 2, may receive a spike from Neuron 4 at time t=1" (Imam, col. 16, lines 48–49).
Neuron 4 is thus one connection removed from Neuron 6 in the path of the spike wave, while Neuron 2 is two connections removed from Neuron 6 in that same path. Neuron 4 (the recited first spiking neuron) is therefore closer to Neuron 6 (the recited first neuron) than Neuron 2 (the recited second spiking neuron) in the path of the spike wave, reading on the recited limitation. Imam further depicts the successive time-step annotations t=0 and t=1 on the arrows from Neuron 6 to Neuron 4 and from Neuron 4 to Neuron 2 at Imam, sheet 8 of 34, FIG. 5C.
Limitation C — a forward depth value of the second spiking neuron is determined based on a spike received from the first spiking neuron
Imam teaches subject matter related to a value of a neuron being determined based on a spike received from a neuron closer to the activated neuron. Specifically, Imam discloses that Neuron 2's spiking response is determined by the spike it receives from Neuron 4: "Neuron 2, may receive a spike from Neuron 4 at time t=1, and Neuron 2 may, in turn, send a spike to propagate the spike wave to Neuron 1" (Imam, col. 16, lines 48–51). Imam further discloses that a synaptic weight is determined based on the receipt of a spike: "As Neuron 4 receives the echo spike one time step removed from Neuron 4 sending a spike (e.g., at t=1 to Neuron 2), Neuron 4 causes the weight of the synapse from Neuron 2 to Neuron 4 to be strengthened" (Imam, col. 16, lines 53–57). Imam further discloses that "a STDP rule may be defined within the SNN of FIGS. 5B-5G such that the weight of a neuron's inbound synapse changes in response to receiving a presynaptic spike (from a neighboring neuron) within a window of time (e.g., a single time step) following the sending of a postsynaptic spike on the neuron" (Imam, col. 16, lines 27–32).
However, Imam does not teach a forward depth value of the second spiking neuron is determined based on a spike received from the first spiking neuron. As set forth in the rejection of Claim 3, the values determined in Imam based on received spikes are the weights of the synapses (Imam, col. 16, lines 27–32, 53–57), and the state variables stored at the neurons of Imam are the membrane potential and the dendritic currents (Imam, col. 10, lines 45–47). Imam does not disclose determining, at a neuron, a forward depth value from a spike received from a neuron closer to the activated neuron.
In the same field of endeavor, Aimone teaches a forward depth value of the second spiking neuron is determined based on a spike received from the first spiking neuron.
Aimone discloses that each node computes its own depth value from the value carried by the spike it receives from the neighboring node closer to the source. Specifically, Aimone discloses that "the circuit computes the largest TTL k′ from any of the incoming spikes, and sends a spike encoding k′ − 1 to all its neighbors if k′ ≥ 1" (Aimone, p. 6, right col., § 4.1, ¶ 2). The receiving node thus derives its value from the value carried by the incoming spike, and the value it in turn transmits differs from the value it received by exactly one increment, corresponding to one additional edge traversed from the source.
Aimone further discloses that the value so received expresses the receiving node's distance from the source: "If a node v receives a spike message encoding the value k′ at time t, then there is a path from source vₛ to node v of length t that traverses k − k′ edges" (Aimone, p. 6, right col., § 4.1, ¶ 1). Aimone further discloses that the spikes carrying the value originate at the source node and are relayed neighbor-to-neighbor outward: "At the start, the node corresponding to vₛ sends ⌈log k⌉ spikes to each neighbor encoding the value k − 1" (Aimone, p. 6, right col., § 4.1, ¶ 1), and "At the start, the neuron corresponding to the source vertex vₛ sends a spike to each neighbor. Every other neuron propagates only the first incoming spike it receives (ties are fine) to all its outgoing neighbors" (Aimone, p. 6, left col., § 3, ¶ 2).
Aimone further discloses that the receiving node retains what it derives from the received spike: "Each node needs to remember a neighbor that sends the first spike. Each node has a unique ID from 0 to n − 1. When node v receives its first spike from node u, it sends a binary encoding of its ID to its neighbors, and 'latches' (remembers) the ID u" (Aimone, p. 6, right col., § 3, ¶ 1).
Applying the teaching of Aimone to the spike wave of Imam, the value at Neuron 2 (the recited second spiking neuron) is computed from the spike Neuron 2 receives from Neuron 4 (the recited first spiking neuron) — which Imam expressly discloses Neuron 2 receiving at t=1 (Imam, col. 16, lines 48–49) — reading on the recited limitation.
Imam and Aimone are analogous to the claimed invention as both are from the same field of endeavor of determining a shortest path through a graph by propagating spikes through a spiking neural network implemented on neuromorphic hardware, for the reasons set forth in the rejection of Claim 3. Imam is directed to "utilizing STDP in an example SNN to determine a shortest path between any two nodes in a network modeled by the SNN" (Imam, col. 15, lines 32–35). Aimone is directed to "neuromorphic graph algorithms, focusing on shortest path problems" executed in "networks consisting of spiking artificial neurons" (Aimone, p. 1, Abstract), and identifies Intel's Loihi neuromorphic processor as a target platform (Aimone, p. 1, right col., § 1, ¶ 1).
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to combine the spike wave of Imam, in which Neuron 2 receives a spike from Neuron 4 that is itself one connection removed from the activated Neuron 6, with the teaching of Aimone that each node computes its depth value from the value carried by the incoming spike and decrements that value by one increment before relaying it, such that the forward depth value of Neuron 2 is determined based on the spike Neuron 2 receives from Neuron 4.
The motivation to combine Imam and Aimone is as recited by Aimone, which teaches that deriving each node's depth value from the incoming spike and relaying the decremented value is the message-passing mechanism that yields a proven "polynomial-factor advantage" over conventional shortest-path computation (Aimone, p. 1, Abstract).
Claim 10 is rejected based on the same rationale as set forth above with respect to Claim 3.
Claim 11 is rejected based on the same rationale as set forth above with respect to Claim 4.
Claim 17 recites limitations that correspond in scope to the limitations of Claim 3. Claim 17 is rejected based on the same rationale as set forth above with respect to Claim 3.
Claim 18 recites limitations that correspond in scope to the limitations of Claim 4. Claim 18 is rejected based on the same rationale as set forth above with respect to Claim 4.
Claims 5, 12, and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Imam in view of Krichmar, further in view of Aimone, and further in view of Madkour et al. (Madkour), Non-Patent Literature, "A Survey of Shortest-Path Algorithms," arXiv:1705.02044v1 [cs.DS], published May 4, 2017, cited in the IDS filed on 7/5/23.
As to dependent Claim 5, the limitations of Claim 1 and Claim 3, from which Claim 5 depends, are taught by the combination of Imam and Aimone under the same rationale set forth above with respect to Claim 1 and Claim 3. Claim 5 further recites:
each spiking neuron stores a backward depth value that is determined based on a spike from the second neuron in the backward spike propagation.
Regarding Claim 5, Imam teaches:
The combination of Imam and Aimone teaches subject matter related to a spiking neuron storing a depth value that is determined based on a received spike. As set forth in the rejection of Claims 3 and 4, Aimone discloses that "Our algorithms must store information at graph nodes. We may use neurons with no leakage or self-loops to preserve state" (Aimone, p. 5, left col., ¶ "Neuromorphic memory"), and that "the circuit computes the largest TTL k′ from any of the incoming spikes, and sends a spike encoding k′ − 1 to all its neighbors if k′ ≥ 1" (Aimone, p. 6, right col., § 4.1, ¶ 2).
However, the combination of Imam and Aimone does not teach each spiking neuron stores a backward depth value that is determined based on a spike from the second neuron in the backward spike propagation. The depth value of Aimone is generated by a single propagation originating at the source node only: "At the start, the neuron corresponding to the source vertex vₛ sends a spike to each neighbor. Every other neuron propagates only the first incoming spike it receives (ties are fine) to all its outgoing neighbors. The NGA terminates when the neuron corresponding to the destination node receives a spike" (Aimone, p. 6, left col., § 3, ¶ 2), and the value that results indicates distance from that same source: "there is a path from source vₛ to node v of length t that traverses k − k′ edges" (Aimone, p. 6, right col., § 4.1, ¶ 1). Aimone performs no second propagation from the opposite endpoint and therefore discloses no second, backward depth value. Imam, as set forth in the rejection of Claim 3, stores at its neurons only "two types of state variables: one membrane potential v(t), and one or more dendritic current(s)" (Imam, col. 10, lines 45–47), and adjusts only the weights of the synapses in response to spikes (Imam, col. 16, lines 27–32).
In the same field of endeavor, Madkour teaches each spiking neuron stores a backward depth value that is determined based on a spike from the second neuron in the backward spike propagation.
Madkour discloses that each vertex of a graph is assigned and stores two distinct distance labels — a forward label expressing distance measured from that vertex, and a reverse label expressing distance measured to that vertex from the opposite direction. Specifically, Madkour discloses that "In the labeling preprocessing stage, each vertex v is computed and assigned a forward label and a reverse label. The forward label encompasses a set of vertices w, where each vertex contains a computed distance dist(v, w) from v. The reverse label consists of a set of vertices u, where each vertex contains a computed distance dist(u, v) to v. These labels are later used in the query stage to determine the vertices that minimize the distance from source to destination" (Madkour, page 13, § 5.5.5 "Hub Labeling"). The reverse label of Madkour, which each vertex stores and which expresses a distance measured toward that vertex, reads on the recited "backward depth value" stored at each spiking neuron.
Madkour further discloses that the reverse label is generated by a search conducted from the opposite endpoint of the path, and that the forward and reverse labels are used together. Specifically, Madkour discloses that "Abraham and Delling [1, 2] propose a labeling scheme that, given a vertex s and t, it considers the sets of vertices visited by the forward contraction hierarchy from s and the reverse contraction hierarchy of t. The contraction hierarchies algorithm computes for the shortest-path the intersection of the forward and reverse sets" (Madkour, page 14, § 5.5.5).
Madkour further discloses that a shortest-path search is conducted in two directions, a forward search and a backward search: "Nannicini et al. [104] propose a bidirectional A* algorithm that restricts the A* search to a set of vertices that are defined by a time-independent algorithm. The bidirectional A algorithm operates in two modes, where the first mode, namely the forward search algorithm, is run on the graph weighted by a specific cost function while the second mode, namely the backward search, is run on the graph weighted by a lower-bound function*" (Madkour, page 17, § 7.2 "Discrete-Time Algorithms"). Madkour further discloses the calculation of distance labels in connection with such a bidirectional search: "Demiryurek et al. [40] propose a technique to speed-up the fastest-path computation over time-dependent spatial graphs. They propose a technique based on the A* bidirectional time-dependent algorithm that operates in two main stages ... Next, they calculate a lower-bound distance label for vertices and borders. The second state is online, where it probes for the fastest path by utilizing a heuristic function based on the computed distance labels" (Madkour, page 17, § 7.2).
Applying the teaching of Madkour to the combination of Imam and Aimone, each spiking neuron of Imam stores, in addition to the forward depth value generated during the spike wave from Neuron 6, a second and backward depth value generated during the chain of spikes originating at Neuron 1 (the recited second neuron), the backward depth value being computed at each neuron from the incoming spike in the manner Aimone teaches — "the circuit computes the largest TTL k′ from any of the incoming spikes, and sends a spike encoding k′ − 1 to all its neighbors" (Aimone, p. 6, right col., § 4.1, ¶ 2) — reading on the recited limitation.
Imam, Aimone, and Madkour are analogous to the claimed invention. Imam and Aimone are from the same field of endeavor of determining a shortest path through a graph by propagating spikes through a spiking neural network implemented on neuromorphic hardware, for the reasons set forth in the rejection of Claim 3. Madkour is analogous to the claimed invention because it is reasonably pertinent to the particular problem with which the inventor was concerned, namely, finding a shortest path between two nodes in a graph. Madkour is directed to shortest-path computation in graphs: "A shortest-path algorithm finds a path containing the minimal cost between two vertices in a graph. A plethora of shortest-path algorithms is studied in the literature that span across multiple disciplines. This paper presents a survey of shortest-path algorithms based on a taxonomy that is introduced in the paper" (Madkour, page 1, Abstract). The present specification identifies precisely this body of art as the problem context of the claimed invention: "Finding the shortest path in a graph problem usually involves application of shortest path algorithms (e.g., the Dijkstra's algorithm), the Bellman-ford algorithm, or heuristics-based search algorithms (e.g., A* search algorithm)" (Specification, ¶ [0012]). Imam likewise identifies the same problem: "it may be desirable to compute a shortest, most efficient, or most preferred path between two nodes. In large complex networks, determining such paths may be a non-trivial and difficult problem" (Imam, col. 15, lines 19–23).
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to combine the spiking-neural-network shortest-path determination of Imam, having a spike wave from Neuron 6 followed by a chain of spikes from Neuron 1, with the per-neuron stored depth value computed from the incoming spike as taught by Aimone, and further with the assignment to each vertex of both a forward label and a reverse label as taught by Madkour, such that each spiking neuron of Imam stores a backward depth value determined based on a spike from Neuron 1 in the chain of spikes.
The motivation to combine Imam, Aimone, and Madkour is as recited by Madkour, which teaches that assigning each vertex both a forward label and a reverse label yields a query algorithm that "is fast" and "decreases the computation time and reduces the storage complexity significantly" (Madkour, page 13, § 5.5.5; page 17, § 7.2).
Claim 12 recites limitations that correspond in scope to the limitations of Claim 5. Claim 12 is rejected based on the same rationale as set forth above with respect to Claim 5.
Claim 19 recites limitations that correspond in scope to the limitations of Claim 5. Claim 19 is rejected based on the same rationale as set forth above with respect to Claim 5.
Claims 6, 13, and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Imam et al. (Imam), U.S. Patent No. US 10,885,425 B2, patented January 5, 2021, in view of Aimone et al. (Aimone), Non-Patent Literature, "Provable Advantages for Graph Algorithms in Spiking Neural Networks," SPAA '21: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, pages 35–47, published July 6–8, 2021, further in view of Madkour et al. (Madkour), Non-Patent Literature, "A Survey of Shortest-Path Algorithms," arXiv:1705.02044v1 [cs.DS], published May 4, 2017, cited in the IDS filed on 7/5/23, and further in view of Krichmar et al. (Krichmar), Non-Patent Literature, "Flexible Path Planning in a Spiking Model of Replay and Vicarious Trial and Error," From Animals to Animats 16, SAB 2022, Lecture Notes in Artificial Intelligence vol. 13499, pages 177–189, published 2022.
As to dependent Claim 6, the limitations of Claim 1, Claim 3, and Claim 5, from which Claim 6 depends, are taught by the combination of Imam, Aimone, and Madkour under the same rationale set forth above with respect to Claim 1, Claim 3, and Claim 5. Claim 6 further recites:
identifying the path in the graph comprises:
determining that a node in the graph is on the path based on a determination that a forward depth value of a spiking neuron encoding the node matches a backward depth value of the spiking neuron encoding the node.
Regarding Claim 6, Imam teaches identifying the path in the graph comprises: determining that a node in the graph is on the path.
Imam discloses "determine that the path comprises a shortest path in the particular network from a first network node represented by the second neuron to a second network node represented by the first neuron" (Imam, col. 50, lines 26–29). Imam further discloses that the constituent nodes of the path are identified individually: "Monitoring and/or reporting logic may be provided to identify the order and source of spikes sent in this chain of spikes" (Imam, col. 18, lines 62–64), and "A corresponding physical location may be determined for each neuron sending a spike in the spike chain to determine a shortest path to the physical destination environment (e.g., by navigating, in order, through each one of the locations corresponding to the neurons (e.g., Neurons A-F) in the spike chain)" (Imam, col. 22, lines 47–54). Imam further discloses "logic to generate path data to describe the path" (Imam, col. 43, lines 40–41).
The combination of Imam, Aimone, and Madkour teaches subject matter related to a spiking neuron holding a forward depth value and a backward depth value. As set forth in the rejections of Claims 3 and 5, Aimone discloses that "Our algorithms must store information at graph nodes. We may use neurons with no leakage or self-loops to preserve state" (Aimone, p. 5, left col., ¶ "Neuromorphic memory") and that "the circuit computes the largest TTL k′ from any of the incoming spikes, and sends a spike encoding k′ − 1 to all its neighbors if k′ ≥ 1" (Aimone, p. 6, right col., § 4.1, ¶ 2); and Madkour discloses that "each vertex v is computed and assigned a forward label and a reverse label" (Madkour, page 13, § 5.5.5).
However, the combination of Imam, Aimone, and Madkour does not teach determining that a node in the graph is on the path based on a determination that a forward depth value of a spiking neuron encoding the node matches a backward depth value of the spiking neuron encoding the node. Imam determines path membership by comparing a synaptic weight against a globally raised spike potential threshold (Imam, col. 18, lines 22–29). Madkour determines path membership by summing the forward and reverse labels and minimizing the sum — "finding the minimum distance from (Lout(s), x) to (x, Lin(t))" (Madkour, page 14, § 5.5.5) — and by computing "the intersection of the forward and reverse sets" (Madkour, page 14, § 5.5.5), rather than by determining that the two values match.
In the same field of endeavor, Krichmar teaches determining that a node in the graph is on the path based on a determination that a forward depth value of a spiking neuron encoding the node matches a backward depth value of the spiking neuron encoding the node.
Krichmar discloses a spiking neural network in which each node of a graph is encoded in a single neuron: "The spiking wavefront propagation algorithm assumes a grid representation of space. Each grid unit corresponds to a discretized area of physical space, and connections between units represent the ability to travel from one grid location to a neighboring location. Each unit in the grid is represented by a single neuron with spiking dynamics" (Krichmar, page 179, § 2.1).
Krichmar discloses a forward spike propagation originating at a first neuron, and the storing, for each spiking neuron, of a forward depth value indicating that neuron's distance from the first neuron: "the neuron corresponding to the current location (1,1) is induced to spike. This causes an input current to be sent to neighboring neurons, starting a traveling wave of activity across the area covered by the grid. As each neuron spikes, the spike index and the time of spike are logged in a table" (Krichmar, page 181, § 2.3). The logged spike time of each neuron is a forward depth value, because the wave originates at the neuron encoding location (1,1) and reaches each other neuron after an elapsed time determined by the accumulated axonal delays along the route from (1,1), such that the spike time indicates that neuron's distance from the neuron encoding location (1,1).
Krichmar discloses a backward depth value that is initialized at the second neuron to that second neuron's own forward depth value and is thereafter decremented: "To extract a path from the spike table, a list of neuron IDs is maintained, starting with the goal neuron. The first spike time of the goal neuron is found. Then, the timestamps are decremented" (Krichmar, page 181, § 2.3).
Krichmar discloses determining that a node is on the path based on a determination that the forward depth value of the neuron encoding that node matches the backward depth value: "Then, the timestamps are decremented until the spiking of a neuron neighboring the goal neuron is found. The process then continues by finding spikes of neurons neighboring the most recent neuron. The process is repeated until the start neuron is found. The result is an optimal path between the start and goal" (Krichmar, page 181, § 2.3; see also Krichmar, page 181, Fig. 1B, captioned "Example of using the spike table for extracting a path from (1,1) to (4,4). The extracted path is shown in red font"). In Krichmar, a neighboring neuron is determined to lie on the extracted path when, and only when, that neuron's logged forward spike time is found to equal the current decremented timestamp — that is, when the neuron's forward depth value matches the backward depth value obtained by decrementing from the goal neuron's forward depth value. The neuron so found is added to the maintained list of neuron IDs constituting the path.
The recited "first neuron" reads on the neuron encoding location (1,1) of Krichmar, and the recited "second neuron" reads on the goal neuron encoding location (4,4) of Krichmar.
Imam, Aimone, Madkour, and Krichmar are analogous to the claimed invention. Imam, Aimone, and Krichmar are from the same field of endeavor of determining a shortest path through a graph by propagating spikes through a network of spiking neurons in which each graph node is encoded in a neuron. Imam is directed to "utilizing STDP in an example SNN to determine a shortest path between any two nodes in a network modeled by the SNN" (Imam, col. 15, lines 32–35). Aimone is directed to "neuromorphic graph algorithms, focusing on shortest path problems" (Aimone, p. 1, Abstract). Krichmar is directed to a "spiking wavefront propagation algorithm" in which "Each unit in the grid is represented by a single neuron with spiking dynamics" and which yields "an optimal path between the start and goal" (Krichmar, page 179, § 2.1; page 181, § 2.3). Madkour is analogous because it is reasonably pertinent to the particular problem with which the inventor was concerned, namely finding a shortest path between two nodes in a graph (Madkour, page 1, Abstract; Specification, ¶ [0012]), for the reasons set forth in the rejection of Claim 5.
Further evidencing that Krichmar is analogous art, Imam itself cites earlier work by the same first-named author in the same field on its face: "Kichmar Jeffrey L: 'Path planning using a spiking neuron algorithm with axonal delays', 2016 IEEE Congress on Evolutionary Computation (CEC), IEEE, Jul. 24, 2016, 8 pgs." (Imam, page 2, References Cited, Other Publications).
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to combine the spiking-neural-network shortest-path determination of Imam, having a spike wave from Neuron 6 followed by a chain of spikes from Neuron 1, with the per-neuron stored depth value computed from the incoming spike and decremented at each hop as taught by Aimone, and with the assignment to each vertex of both a forward label and a reverse label as taught by Madkour, and further to determine that a node is on the identified path by determining that the node's forward depth value matches its backward depth value, as taught by Krichmar.
The motivation to combine Imam, Aimone, Madkour, and Krichmar is as recited by Krichmar, which teaches that a timing-and-delay-based representation "fits better with the idea behind wave propagation than the more commonly used synaptic weight updates" and that the resulting decrement-and-match extraction yields "an optimal path between the start and goal" (Krichmar, page 179, § 2.1; page 181, § 2.3).
Claim 13 recites limitations that correspond in scope to the limitations of Claim 6. Claim 13 is rejected based on the same rationale as set forth above with respect to Claim 6.
Claim 20 recites limitations that correspond in scope to the limitations of Claim 6. Claim 20 is rejected based on the same rationale as set forth above with respect to Claim 6.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to HUNG VAN LE whose telephone number is (571)270-0164. The examiner can normally be reached 8 a.m. - 5 p.m..
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, Cesar Paula can be reached at (571) 272-4128. 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.
/HUNG VAN LE/Examiner, Art Unit 2145
/CESAR B PAULA/Supervisory Patent Examiner, Art Unit 2145
Prosecution Insights