DETAILED CORRESPONDENCE
This is the first office action regarding application number 19/338,098, filed on 24 September 2025.
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 .
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 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.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 13-16 rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Regarding Claims 13-16
Claim 13 recites "wherein the system is installed in a mobile body,", but the preamble of independent claim 1 already recites "a mobile body". Accordingly, it is unclear whether there are one or two mobile bodies being claimed. As such, the claim is indefinite because the metes and bounds of the claim are unclear. Claims 14-16 are rejected by virtue of dependency on claim 13. For the purpose of compact prosecution, the claim will be interpreted as if only reciting one mobile body.
Regarding Claim 14
There is insufficient antecedent basis for "the edge" in the claim and it is unclear whether "the edge" is referring to "the first edge" from claim 1 or a new distinct edge. As such, the claim is indefinite because the metes and bounds of the claim are unclear. For the purpose of compact prosecution, the claim will be interpreted as if only reciting one edge.
Regarding Claim 15
There is insufficient antecedent basis for "the current position" in the claim. As such, the claim is indefinite because the metes and bounds of the claim are unclear. For the purpose of compact prosecution, "the current position" will be interpreted as "a current position".
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-12 and 17-18 are rejected under 35 U.S.C. 101 because the claimed invention is directed to mental processes without significantly more.
Regarding Claim 1
Claim 1 recites a system configured to control a mobile body to move in accordance with movement of a person, the system comprising:
one or more memories storing instructions; and one or more processors that execute the instructions to:
acquire information indicating a position and a moving direction of a person;
acquire a graph that includes nodes and edges and indicates a movement route of the person;
determine a first edge of the graph corresponding to the position of the person based on the position of the person; and
decide a movement target position of the mobile body based on the first edge or on one or more edges located in the moving direction of the person with respect to the first edge.
Claim analysis via 2019 PEG
Step 1: Statutory Category – Yes
The claim recites one or more processors. Thus, the claim falls within one of the four statutory categories because the claim is to a manufacture/machine. See MPEP 2106.03.
Step 2A Prong One Evaluation: Judicial Exception – Yes – Mental processes
Claims are to be analyzed to determine whether it recites subject matter that falls within one of the following groups of abstract ideas: a) mathematical concepts, b) mental processes, and/or c) certain methods of organizing human activity.
The Office submits that the foregoing bolded limitation(s) constitutes judicial exceptions in terms of “mental processes” because under its broadest reasonable interpretation, the claim covers performance of the limitation in the human mind.
The claim recites the limitations of “acquire a graph that includes nodes and edges and indicates a movement route of the person;”, determine a first edge of the graph corresponding to the position of the person based on the position of the person;” “decide a movement target position of the mobile body based on the first edge or on one or more edges located in the moving direction of the person with respect to the first edge.” These limitations, as drafted, are a process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind but for the recitation of the generic computer component “processor(s)”. That is, other than reciting the “processor(s)”, nothing in the claim elements precludes the step from practically being performed in the mind with the aid of pen and paper. For example, but for the generic computer language, the claim encompasses a human mentally or physically drawing a graph with nodes and edges indicating a movement route of a person, determining an edge of the graph corresponding to a position of the person and deciding a movement target position of a robot based on the position of the person and the corresponding edge of the graph. The mere nominal recitation of the processor(s) does not take the claim limitations out of the mental process grouping. Thus, the claim recites a mental process.
Accordingly, the claim is directed to an abstract idea.
Step 2A Prong Two Evaluation: Practical Application - No
The claims are evaluated whether as a whole they integrate the recited judicial exception into a practical application. As noted in the 2019 PEG, it must be determined whether any additional elements in the claim beyond the abstract idea integrate the exception into a practical application in a manner that imposes a meaningful limit on the judicial exception. The courts have indicated that additional elements merely using a computer to implement an abstract idea, adding insignificant extra solution activity, or generally linking use of a judicial exception to a particular technological environment or field of use do not integrate a judicial exception into a “practical application.”
In the present case, the additional limitations beyond the above-noted abstract idea are as follows (where the underlined portions are the “additional limitations” while the bolded portions continue to represent the “abstract idea”).
The claim recites additional elements “one or more memories storing instructions; and one or more processors that execute the instructions to:”. The memory and processor do not integrate the abstract idea into a practical application because they are described at high level of generality and are merely computer components being used as a tool to perform the abstract idea. See MPEP 2106.04(d)(I).
The claim recites an additional step of “acquire information indicating a position and a moving direction of a person;”. The acquiring information step is recited at a high level of generality (i.e. as a general means of gathering position data for use in the remaining mental steps) and amounts to mere data gathering, which is a form of insignificant extra-solution activity. See MPEP 2106.05(g).
Accordingly, even in combination, these additional elements do not integrate the abstract idea into a practical application because they do not impose any meaningful limits on practicing the abstract idea.
Accordingly, the claim is directed to an abstract idea.
Step 2B Evaluation: Inventive concept - No
The claim(s) is evaluated whether the claim as a whole amounts to significantly more than the recited exception, i.e., whether any additional element, or combination of additional elements, adds an inventive concept to the claim.
The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception. As discussed with respect to Step 2A Prong Two, for the additional elements in the claim in which the memory and processor are merely a tool being used to perform the abstract idea, the same analysis applies here as above. Merely using a computer as a tool to perform an abstract idea cannot integrate a judicial exception into a practical application or provide an inventive concept.
Under the 2019 PEG, a conclusion that an additional element is insignificant extra-solution activity in Step 2A should be re-evaluated in Step 2B. Here, the data gathering step was considered to be insignificant extra-solution activity in Step 2A, and thus it is re-evaluated in Step 2B to determine if it is more than what is well-understood, routine, conventional activity in the field.
The specification recites that the control unit including the processor and memory is a conventional controller and does not provide any indication that it is anything other than conventional computer equipment. MPEP 2106.05(d)(II), and the cases cited therein, including Intellectual Ventures I, LLC v. Symantec Corp., 838 F.3d 1307, 1321 (Fed. Cir. 2016), TLI Communications LLC v. AV Auto. LLC, 823 F.3d 607, 610 (Fed. Cir. 2016), and OIP Techs., Inc., v. Amazon.com, Inc., 788 F.3d 1359, 1363 (Fed. Cir. 2015), indicate that mere collection or receipt of data over a network is a well‐understood, routine, and conventional function when it is claimed in a merely generic manner (as it is here).
Claim 1 is not patent eligible.
Regarding Claims 2-12
Claim 2 recites the system according to claim 1,
wherein the one or more processors execute the instructions to decide the movement target position of the mobile body based on a position corresponding to a point on the first edge or the one or more edges located in the moving direction of the person with respect to the first edge.
Claim 3 recites the system according to claim 1,
wherein the one or more processors execute the instructions to decide the movement target position of the mobile body based on a plurality of edges connected to the first edge at a first node located in the moving direction of the person among nodes to which the first edge is connected.
Claim 4 recites the system according to claim 3,
wherein the one or more processors execute the instructions to evaluate probabilities that the person passes through routes corresponding to each of the plurality of edges connected to the first edge, and decide, as the movement target position of the mobile body, a position on a route obtained by weighting and combining the routes corresponding to each of the plurality of edges in accordance with the probabilities.
Claim 5 recites the system according to claim 1,
wherein the one or more processors execute the instructions to decide the movement target position in such a way that the mobile body leads or follows the person.
Claim 6 recites the system according to claim 1,
wherein the one or more processors execute the instructions to update the graph to delete an edge based on a determination that an obstacle is present on the edge.
Claim 7 recites the system according to claim 1,
wherein the one or more processors execute the instructions to update the graph to offset an edge based on a determination that an obstacle is present on the edge.
Claim 8 recites the system according to claim 1,
wherein the one or more processors execute the instructions to update the graph to correct or delete an edge in a manner dependent on a size of an obstacle present on the edge based on a determination that the obstacle is present on the edge.
Claim 9 recites the system according to claim 8,
wherein the one or more processors execute the instructions to update the graph to delete the edge when a ratio of a length of a portion of the edge passing through a region of the obstacle to a length of the edge is larger than a threshold.
Claim 10 recites the system according to claim 9,
wherein the one or more processors execute the instructions to update the graph to offset the edge when the ratio of the length of the portion of the edge passing through the region of the obstacle to the length of the edge is equal to or smaller than the threshold.
Claim 11 recites the system according to claim 1,
wherein the one or more processors execute the instructions to:
estimate a position of the mobile body based on an output from a sensor included in the mobile body, and generate an environment map in a coordinate system based on the mobile body as a reference; and
decide the movement target position of the mobile body based on the graph converted into the coordinate system based on the mobile body as the reference and aligned with the environment map.
Claim 12 recites the system according to claim 11,
wherein the one or more processors execute the instructions to transform the graph and align the graph with the environment map to alleviate a change in a conversion result of the graph caused by a change in the coordinate system based on the mobile body as the reference.
Claim analysis via 2019 PEG
Step 1: Statutory category – Yes
The claims recite one or more processors. Thus, the claims fall within one of the four statutory categories because the claims are to a manufacture/machine. See MPEP 2106.03.
Step 2A Prong One Evaluation: Judicial Exception – Yes – Mental processes
Claims are to be analyzed to determine whether it recites subject matter that falls within one of the following groups of abstract ideas: a) mathematical concepts, b) mental processes, and/or c) certain methods of organizing human activity.
The Office submits that the foregoing bolded limitation(s) constitutes judicial exceptions in terms of “mental processes” because under its broadest reasonable interpretation, the claims cover performance of the limitation in the human mind.
Regarding claim 2, the claim recites the limitation of “decide the movement target position of the mobile body based on a position corresponding to a point on the first edge or the one or more edges located in the moving direction of the person with respect to the first edge.”. This limitation, as drafted, is a process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind but for the recitation of the generic computer component “processor(s)”. That is, other than reciting the “processor(s)”, nothing in the claim elements precludes the step from practically being performed in the mind with the aid of pen and paper. For example, but for the generic computer language, the claim encompasses the human performing the mental steps discussed above, by further deciding a movement target position of the robot based on a position corresponding to a point on the first edge. Thus, the claim recites a mental process.
Regarding claim 3, the claim recites the limitation of “decide the movement target position of the mobile body based on a plurality of edges connected to the first edge at a first node located in the moving direction of the person among nodes to which the first edge is connected.”. This limitation, as drafted, is a process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind but for the recitation of the generic computer component “processor(s)”. That is, other than reciting the “processor(s)”, nothing in the claim elements precludes the step from practically being performed in the mind with the aid of pen and paper. For example, but for the generic computer language, the claim encompasses the human performing the mental steps discussed above, by further deciding a movement target position of the robot based on a plurality of edges connected to the first edge at a first node located in the moving direction of the person. Thus, the claim recites a mental process.
Regarding claim 4, the claim recites the limitation of “evaluate probabilities that the person passes through routes corresponding to each of the plurality of edges connected to the first edge, and decide, as the movement target position of the mobile body, a position on a route obtained by weighting and combining the routes corresponding to each of the plurality of edges in accordance with the probabilities.”. This limitation, as drafted, is a process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind but for the recitation of the generic computer component “processor(s)”. That is, other than reciting the “processor(s)”, nothing in the claim elements precludes the step from practically being performed in the mind with the aid of pen and paper. For example, but for the generic computer language, the claim encompasses the human performing the mental steps discussed above, by further evaluating probabilities that a person pass through each route and deciding a movement position of the robot accordingly. Thus, the claim recites a mental process.
Regarding claim 5, the claim recites the limitation of “decide the movement target position in such a way that the mobile body leads or follows the person.”. This limitation, as drafted, is a process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind but for the recitation of the generic computer component “processor(s)”. That is, other than reciting the “processor(s)”, nothing in the claim elements precludes the step from practically being performed in the mind with the aid of pen and paper. For example, but for the generic computer language, the claim encompasses the human performing the mental steps discussed above, by further deciding a moving position of the robot to follow the person. Thus, the claim recites a mental process.
Regarding claim 6, the claim recites the limitation of “update the graph to delete an edge based on a determination that an obstacle is present on the edge.”. This limitation, as drafted, is a process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind but for the recitation of the generic computer component “processor(s)”. That is, other than reciting the “processor(s)”, nothing in the claim elements precludes the step from practically being performed in the mind with the aid of pen and paper. For example, but for the generic computer language, the claim encompasses the human performing the mental steps discussed above, by further updating the graph by deleting an edge after detecting an obstacle. Thus, the claim recites a mental process.
Regarding claim 7, the claim recites the limitation of “update the graph to offset an edge based on a determination that an obstacle is present on the edge.”. This limitation, as drafted, is a process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind but for the recitation of the generic computer component “processor(s)”. That is, other than reciting the “processor(s)”, nothing in the claim elements precludes the step from practically being performed in the mind with the aid of pen and paper. For example, but for the generic computer language, the claim encompasses the human performing the mental steps discussed above, by further updating the graph to offset an edge after detecting an obstacle. Thus, the claim recites a mental process.
Regarding claim 8, the claim recites the limitation of “update the graph to correct or delete an edge in a manner dependent on a size of an obstacle present on the edge based on a determination that the obstacle is present on the edge.”. This limitation, as drafted, is a process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind but for the recitation of the generic computer component “processor(s)”. That is, other than reciting the “processor(s)”, nothing in the claim elements precludes the step from practically being performed in the mind with the aid of pen and paper. For example, but for the generic computer language, the claim encompasses the human performing the mental steps discussed above, by further updating the graph to correct or delete an edge depending on a detected obstacle. Thus, the claim recites a mental process.
Regarding claim 9, the claim recites the limitation of “update the graph to delete the edge when a ratio of a length of a portion of the edge passing through a region of the obstacle to a length of the edge is larger than a threshold.”. This limitation, as drafted, is a process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind but for the recitation of the generic computer component “processor(s)”. That is, other than reciting the “processor(s)”, nothing in the claim elements precludes the step from practically being performed in the mind with the aid of pen and paper. For example, but for the generic computer language, the claim encompasses the human performing the mental steps discussed above, by further updating the graph to delete an edge based on a ration of a length of the edge passing through a region of an obstacle. Thus, the claim recites a mental process.
Regarding claim 10, the claim recites the limitation of “update the graph to offset the edge when the ratio of the length of the portion of the edge passing through the region of the obstacle to the length of the edge is equal to or smaller than the threshold.”. This limitation, as drafted, is a process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind but for the recitation of the generic computer component “processor(s)”. That is, other than reciting the “processor(s)”, nothing in the claim elements precludes the step from practically being performed in the mind with the aid of pen and paper. For example, but for the generic computer language, the claim encompasses the human performing the mental steps discussed above, by further updating the graph to offset the edge when the ratio of the length of the portion of the edge passing through the region of the obstacle to the length of the edge is equal to or smaller than the threshold. Thus, the claim recites a mental process.
Regarding claim 11, the claim recites the limitations of “estimate a position of the mobile body based on an output from a sensor included in the mobile body, and generate an environment map in a coordinate system based on the mobile body as a reference;” and “decide the movement target position of the mobile body based on the graph converted into the coordinate system based on the mobile body as the reference and aligned with the environment map.”. These limitations, as drafted, are a process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind but for the recitation of the generic computer component “processor(s)”. That is, other than reciting the “processor(s)”, nothing in the claim elements precludes the step from practically being performed in the mind with the aid of pen and paper. For example, but for the generic computer language, the claim encompasses the human performing the mental steps discussed above, by further estimating a position of the robot based on sensor information and deciding a movement target position of the robot based on a coordinate system of the robot. Thus, the claim recites a mental process.
Regarding claim 12, the claim recites the limitation of “transform the graph and align the graph with the environment map to alleviate a change in a conversion result of the graph caused by a change in the coordinate system based on the mobile body as the reference.”. This limitation, as drafted, is a process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind but for the recitation of the generic computer component “processor(s)”. That is, other than reciting the “processor(s)”, nothing in the claim elements precludes the step from practically being performed in the mind with the aid of pen and paper. For example, but for the generic computer language, the claim encompasses the human performing the mental steps discussed above, by further transforming the graph and aligning the graph with the environment map to alleviate a change in a conversion result of the graph caused by a change in the coordinate system based on the mobile body as the reference. Thus, the claim recites a mental process.
Accordingly, the claims are directed to an abstract idea.
Step 2A Prong Two Evaluation: Practical Application - No
The claims are evaluated whether as a whole they integrate the recited judicial exception into a practical application. As noted in the 2019 PEG, it must be determined whether any additional elements in the claim beyond the abstract idea integrate the exception into a practical application in a manner that imposes a meaningful limit on the judicial exception. The courts have indicated that additional elements merely using a computer to implement an abstract idea, adding insignificant extra solution activity, or generally linking use of a judicial exception to a particular technological environment or field of use do not integrate a judicial exception into a “practical application.”
In the present case, the additional limitations beyond the above-noted abstract idea are as follows (where the underlined portions are the “additional limitations” while the bolded portions continue to represent the “abstract idea”).
Claims 2-12 recite an additional element “wherein the one or more processors execute the instructions to:”. The “processor(s)” does not integrate the abstract idea into a practical application because it is described at high level of generality and is merely a computer component being used as a tool to perform the abstract idea. See MPEP 2106.04(d)(I).
Accordingly, even in combination, these additional elements do not integrate the abstract idea into a practical application because they do not impose any meaningful limits on practicing the abstract idea.
Accordingly, the claims are directed to an abstract idea.
Step 2B Evaluation: Inventive concept - No
The claim(s) is evaluated whether the claim as a whole amounts to significantly more than the recited exception, i.e., whether any additional element, or combination of additional elements, adds an inventive concept to the claim.
The claims do not include additional elements that are sufficient to amount to significantly more than the judicial exception. As discussed with respect to Step 2A Prong Two, for the additional elements in the claims in which the “processor(s)” is merely a tool being used to perform the abstract idea, the same analysis applies here as above. Merely using a computer as a tool to perform an abstract idea cannot integrate a judicial exception into a practical application or provide an inventive concept.
Claims 2-12 are not patent eligible.
Regarding Claim 17
Claim 17 recites a method of controlling a mobile body to move in accordance with movement of a person, the method comprising:
acquiring information indicating a position and a moving direction of a person;
acquiring a graph that includes nodes and edges and indicates a movement route of the person;
determining a first edge of the graph corresponding to the position of the person based on the position of the person; and
deciding a movement target position of the mobile body based on the first edge or on one or more edges located in the moving direction of the person with respect to the first edge.
Claim analysis via 2019 PEG
Step 1: Statutory Category – Yes
The claim recites a method including at least one step. The claim falls within one of the four statutory categories because the claim is to a process. See MPEP 2106.03.
Step 2A Prong One Evaluation: Judicial Exception – Yes – Mental processes
Claims are to be analyzed to determine whether it recites subject matter that falls within one of the following groups of abstract ideas: a) mathematical concepts, b) mental processes, and/or c) certain methods of organizing human activity.
The Office submits that the foregoing bolded limitation(s) constitutes judicial exceptions in terms of “mental processes” because under its broadest reasonable interpretation, the claim covers performance of the limitation in the human mind.
The claim recites the limitations of “acquiring a graph that includes nodes and edges and indicates a movement route of the person;”, determining a first edge of the graph corresponding to the position of the person based on the position of the person;” “deciding a movement target position of the mobile body based on the first edge or on one or more edges located in the moving direction of the person with respect to the first edge.” These limitations, as drafted, are a process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind. That is, nothing in the claim elements precludes the step from practically being performed in the mind with the aid of pen and paper. For example the claim encompasses a human mentally or physically drawing a graph with nodes and edges indicating a movement route of a person, determining an edge of the graph corresponding to a position of the person and deciding a movement target position of a robot based on the position of the person and the corresponding edge of the graph. Thus, the claim recites a mental process.
Accordingly, the claim is directed to an abstract idea.
Step 2A Prong Two Evaluation: Practical Application - No
The claims are evaluated whether as a whole they integrate the recited judicial exception into a practical application. As noted in the 2019 PEG, it must be determined whether any additional elements in the claim beyond the abstract idea integrate the exception into a practical application in a manner that imposes a meaningful limit on the judicial exception. The courts have indicated that additional elements merely using a computer to implement an abstract idea, adding insignificant extra solution activity, or generally linking use of a judicial exception to a particular technological environment or field of use do not integrate a judicial exception into a “practical application.”
In the present case, the additional limitations beyond the above-noted abstract idea are as follows (where the underlined portions are the “additional limitations” while the bolded portions continue to represent the “abstract idea”).
The claim recites an additional step of “acquiring information indicating a position and a moving direction of a person;”. The acquiring information step is recited at a high level of generality (i.e. as a general means of gathering position data for use in the remaining mental steps) and amounts to mere data gathering, which is a form of insignificant extra-solution activity. See MPEP 2106.05(g).
Accordingly, even in combination, these additional elements do not integrate the abstract idea into a practical application because they do not impose any meaningful limits on practicing the abstract idea.
Accordingly, the claim is directed to an abstract idea.
Step 2B Evaluation: Inventive concept - No
The claim(s) is evaluated whether the claim as a whole amounts to significantly more than the recited exception, i.e., whether any additional element, or combination of additional elements, adds an inventive concept to the claim.
The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception. Under the 2019 PEG, a conclusion that an additional element is insignificant extra-solution activity in Step 2A should be re-evaluated in Step 2B. Here, the data gathering step was considered to be insignificant extra-solution activity in Step 2A, and thus it is re-evaluated in Step 2B to determine if it is more than what is well-understood, routine, conventional activity in the field.
The specification recites that the control unit performing the method claim is a conventional controller and does not provide any indication that it is anything other than conventional computer equipment. MPEP 2106.05(d)(II), and the cases cited therein, including Intellectual Ventures I, LLC v. Symantec Corp., 838 F.3d 1307, 1321 (Fed. Cir. 2016), TLI Communications LLC v. AV Auto. LLC, 823 F.3d 607, 610 (Fed. Cir. 2016), and OIP Techs., Inc., v. Amazon.com, Inc., 788 F.3d 1359, 1363 (Fed. Cir. 2015), indicate that mere collection or receipt of data over a network is a well‐understood, routine, and conventional function when it is claimed in a merely generic manner (as it is here).
Claim 17 is not patent eligible.
Regarding Claim 18
Claim 18 recites a non-transitory computer-readable medium storing a program executable by a computer to perform a method of controlling a mobile body to move in accordance with movement of a person, the method comprising:
acquiring information indicating a position and a moving direction of a person;
acquiring a graph that includes nodes and edges and indicates a movement route of the person;
determining a first edge of the graph corresponding to the position of the person based on the position of the person; and
deciding a movement target position of the mobile body based on the first edge or on one or more edges located in the moving direction of the person with respect to the first edge.
Claim analysis via 2019 PEG
Step 1: Statutory Category – Yes
The claim recites a non-transitory computer-readable medium. Thus, the claim falls within one of the four statutory categories because the claim is to a manufacture/machine. See MPEP 2106.03.
Step 2A Prong One Evaluation: Judicial Exception – Yes – Mental processes
Claims are to be analyzed to determine whether it recites subject matter that falls within one of the following groups of abstract ideas: a) mathematical concepts, b) mental processes, and/or c) certain methods of organizing human activity.
The Office submits that the foregoing bolded limitation(s) constitutes judicial exceptions in terms of “mental processes” because under its broadest reasonable interpretation, the claim covers performance of the limitation in the human mind.
The claim recites the limitations of “acquiring a graph that includes nodes and edges and indicates a movement route of the person;”, determining a first edge of the graph corresponding to the position of the person based on the position of the person;” “deciding a movement target position of the mobile body based on the first edge or on one or more edges located in the moving direction of the person with respect to the first edge.” These limitations, as drafted, are a process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind but for the recitation of the generic computer component “non-transitory computer-readable medium”. That is, other than reciting the “non-transitory computer-readable medium”, nothing in the claim elements precludes the step from practically being performed in the mind with the aid of pen and paper. For example, but for the generic computer language, the claim encompasses a human mentally or physically drawing a graph with nodes and edges indicating a movement route of a person, determining an edge of the graph corresponding to a position of the person and deciding a movement target position of a robot based on the position of the person and the corresponding edge of the graph. The mere nominal recitation of the computer component does not take the claim limitations out of the mental process grouping. Thus, the claim recites a mental process.
Accordingly, the claim is directed to an abstract idea.
Step 2A Prong Two Evaluation: Practical Application - No
The claims are evaluated whether as a whole they integrate the recited judicial exception into a practical application. As noted in the 2019 PEG, it must be determined whether any additional elements in the claim beyond the abstract idea integrate the exception into a practical application in a manner that imposes a meaningful limit on the judicial exception. The courts have indicated that additional elements merely using a computer to implement an abstract idea, adding insignificant extra solution activity, or generally linking use of a judicial exception to a particular technological environment or field of use do not integrate a judicial exception into a “practical application.”
In the present case, the additional limitations beyond the above-noted abstract idea are as follows (where the underlined portions are the “additional limitations” while the bolded portions continue to represent the “abstract idea”).
The claim recites an additional element “non-transitory computer-readable medium”. The non-transitory computer-readable medium does not integrate the abstract idea into a practical application because it is described at high level of generality and is merely a computer component being used as a tool to perform the abstract idea. See MPEP 2106.04(d)(I).
The claim recites an additional step of “acquiring information indicating a position and a moving direction of a person;”. The acquiring information step is recited at a high level of generality (i.e. as a general means of gathering position data for use in the remaining mental steps) and amounts to mere data gathering, which is a form of insignificant extra-solution activity. See MPEP 2106.05(g).
Accordingly, even in combination, these additional elements do not integrate the abstract idea into a practical application because they do not impose any meaningful limits on practicing the abstract idea.
Accordingly, the claim is directed to an abstract idea.
Step 2B Evaluation: Inventive concept - No
The claim(s) is evaluated whether the claim as a whole amounts to significantly more than the recited exception, i.e., whether any additional element, or combination of additional elements, adds an inventive concept to the claim.
The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception. As discussed with respect to Step 2A Prong Two, for the additional elements in the claim in which the non-transitory computer-readable medium is merely a tool being used to perform the abstract idea, the same analysis applies here as above. Merely using a computer as a tool to perform an abstract idea cannot integrate a judicial exception into a practical application or provide an inventive concept.
Under the 2019 PEG, a conclusion that an additional element is insignificant extra-solution activity in Step 2A should be re-evaluated in Step 2B. Here, the data gathering step was considered to be insignificant extra-solution activity in Step 2A, and thus it is re-evaluated in Step 2B to determine if it is more than what is well-understood, routine, conventional activity in the field.
The specification recites that the control unit including the non-transitory computer-readable medium is a conventional controller and does not provide any indication that it is anything other than conventional computer equipment. MPEP 2106.05(d)(II), and the cases cited therein, including Intellectual Ventures I, LLC v. Symantec Corp., 838 F.3d 1307, 1321 (Fed. Cir. 2016), TLI Communications LLC v. AV Auto. LLC, 823 F.3d 607, 610 (Fed. Cir. 2016), and OIP Techs., Inc., v. Amazon.com, Inc., 788 F.3d 1359, 1363 (Fed. Cir. 2015), indicate that mere collection or receipt of data over a network is a well‐understood, routine, and conventional function when it is claimed in a merely generic manner (as it is here).
Claim 18 is not patent eligible.
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.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claims 1-3, 5, 7-8, 13-15 and 17-18 are rejected under 35 U.S.C. 103 as being unpatentable over NPL_Fang - "Dynamic Path Planning..." (Fang hereinafter), in view of Horiuchi (US 20230185317 A1 and Horiuchi hereinafter) .
Regarding Claim 1
Fang teaches a system configured to control a mobile body to move in accordance with movement of a person (see all Figs.; Abstract, all), the system comprising:
one or more memories storing instructions; and one or more processors (see Figs. 6-10, all; Section V. Experiments: "The path for the robot to the goal is computed using the approach described in section IV-A and illustrated in Fig. 8(a).") that execute the instructions to:
acquire information indicating a position and a moving direction of a person (see Section III. Robot Setup and Scenario: "The user who is interacting with the robot is tracked with a multi-modal person detection and tracking system from our previous work [15] combining the camera (face detection), laser (legs detection) and microphone data (sound location), and providing person positions in polar coordinate system with respect to the robot. During the Home-Tour the human movement containing navigation strategies of the guide-person is observed by the robot. All of the person positions obtaining from the tracking system are recorded to build a graph with multiple layers, as will be elaborated on in section IV-A."; Section IV. Path Planning - A. Graph Creation: "The person tracking system provides dense information about person positions calculated in the world frame, namely the occupancy grid map of the environment created by the SLAM component ... Hence, the person positions are inserted as nodes Ni into a graph GNoEdge without connections between the nodes. The creation of edges in the graph will be discussed later on in this section. Considering that during the Home-Tour introduced in section III different locations are shown to the robot one after another, the whole human trajectory (all of the person positions) is segmented into sub-trajectories, where each sub-trajectory illustrates the set of person positions beginning at location A and ending at the subsequent location B shown by the guide-person. In particular the first sub trajectory records the person positions from the beginning of the scenario to the first location, while the last one stores the person trajectory from the last location to the end of the guided tour.");
acquire a graph that includes nodes and edges and indicates a movement route of the person (see Fig. 4, all; Fig. 5, all; Figs. 7-8, all; Section IV. Path Planning - A. Graph Creation: "Hence, the person positions are inserted as nodes Ni into a graph GNoEdge without connections between the nodes … Therefore, each node Ni of the graph GNoEdge can be assigned to a corresponding layer GLayer(Ni)3, and all nodes belonging to a graph layer GLayer represent a sub-trajectory of the guide-person. A virtual grid with a predefined resolution different from the resolution of the occupancy grid map is laid over the built map, and the number of nodes is limited to one per virtual grid cell. The connection of graph nodes is created simply under the restriction of distance. Newly added nodes get connected by an edge to all neighbor nodes whose grid cell distance is smaller than a certain threshold. By this means, nodes lying on different graph layers might be connected, suppose they are nearby each other; while there might be no edge between nodes on the same layer, when they are far from each other."; Section V. Experiments: "Notice that edges connecting nodes from different layers are allowed to realize layer switches, when the sub-trajectories of the person interweave each other.");
determine a first edge of the graph corresponding to the position of the person based on the position of the person (see Figs. 7-8, all, especially "Note that the path with a small detour results from the edge weights defined in formula 1. The green path from NF1 crossing the table is illustrated in b) compared with the red path containing navigation strategies of the guide-person"; Equations (1)-(3); Section IV. Path Planning - A. Graph Creation: "Edges connecting nodes from different layers are allowed. However, they will suffer from a multiplied penalty factor αl on the base of the initial edge weights. This, again, makes graph layer changes rare, although not impossible. Altogether, the path calculated by A is a compromise between the shortest distance way from A to B and an imitation of human behavior which the robot watches during the Home-Tour. Thus, the edge weight ω(Ni,Nj) between two nodes Ni,Nj is defined as follows:…"; Section V. Experiments: "The route of the guide-person began from A, via B, C, D, and ended in proximity to the start position A. The region between A and D corresponds to the corridor of the real environment … The path for the robot to the goal is computed using the approach described in section IV-A and illustrated in Fig. 8(a)."); and
decide a movement target position of the mobile body based on the first edge or on one or more edges (see Fig. 8, all, especially "Note that the path with a small detour results from the edge weights defined in formula 1. The green path from NF1 crossing the table is illustrated in b) compared with the red path containing navigation strategies of the guide-person"; Equations (1)-(3); Section IV. Path Planning - A. Graph Creation: "Edges connecting nodes from different layers are allowed. However, they will suffer from a multiplied penalty factor αl on the base of the initial edge weights. This, again, makes graph layer changes rare, although not impossible. Altogether, the path calculated by A is a compromise between the shortest distance way from A to B and an imitation of human behavior which the robot watches during the Home-Tour. Thus, the edge weight ω(Ni,Nj) between two nodes Ni,Nj is defined as follows:…"; Section V. Experiments: "The route of the guide-person began from A, via B, C, D, and ended in proximity to the start position A. The region between A and D corresponds to the corridor of the real environment … The path for the robot to the goal is computed using the approach described in section IV-A and illustrated in Fig. 8(a)."; Conclusion, all).
Although it is implied, Fang does not explicitly teach decide a movement target position of the mobile body based on the first edge or on one or more edges located in the moving direction of the person with respect to the first edge.
Horiuchi teaches a system configured to control a mobile body to move in accordance with movement of a person (see all Figs., especially Fig. 1; [0001] and [0018]), the system comprising:
one or more memories storing instructions; and one or more processors (see Fig. 23, memory 508 and data processing unit 503; [0361]) that execute the instructions to:
acquire information indicating a position and a moving direction of a person (see Fig. 1 all; [0018] and [0064]-[0083], especially [0076 "The state at time t2 is a state after a determination is made that the tracking target 20 travels along route B between the two routes A and B that form the fork.']-[0077 "Analysis of a selected route of the tracking target 20 is performed, for example, by analyzing a direction or traveling direction of the tracking target from a camera-captured image of the robot 10."]);
acquire a graph that includes a node and edges and indicates a movement route of the person (see Fig. 1 all; [0018] and [0064]-[0083], especially [0068 "In this time t1, the robot 10 cannot estimate or determine which of two routes forming a fork, route A and route B, along which the tracking target 20 will travel."], [0071 "That is, when the robot 10 is set in the goal posture 41 at the goal position 31, it is possible to bring the tracking target 20 within the field of view regardless of one of the two routes including route A or route B along which the tracking target 20 travels, and it is possible to continue the tracking processing without losing sight of the tracking target 20."] and [0076 "The state at time t2 is a state after a determination is made that the tracking target 20 travels along route B between the two routes A and B that form the fork."]);
determine a first edge of the graph corresponding to the position of the person based on the position of the person (see Fig. 1, route B; [0076 "The state at time t2 is a state after a determination is made that the tracking target 20 travels along route B between the two routes A and B that form the fork."] and [0077]-[0078 "After a determination is made that the tracking target 20 travels along route B,..."]); and
decide a movement target position of the mobile body based on the first edge or on one or more edges located in the moving direction of the person with respect to the first edge (see Fig. 1, goal position 32 and/or goal route 52; [0076]-[0078 "After a determination is made that the tracking target 20 travels along route B, the goal position 32, the goal posture 42 and the goal route 52 are changed from the goal position 31, the goal posture 41 and the goal route 51 shown in FIG. 1 (1), respectively, and updated, as illustrated in FIG. 1 (2). In this case, a range of viewing angle (θ) includes only route B that is a selected route of the tracking target 20."] and [0083]).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to modify the system of Fang to decide a movement target position of the mobile body based on the first edge or on one or more edges located in the moving direction of the person with respect to the first edge, as taught by Horiuchi, in order to efficiently follow and track the person with an optimal posture to avoid losing sight of the person.
Regarding Claim 2
Modified Fang teaches the system according to claim 1 (as discussed above in claim 1),
Fang further teaches wherein the one or more processors execute the instructions to decide the movement target position of the mobile body based on a position corresponding to a point on the first edge or the one or more edges (see Fig. 8, all, especially "Note that the path with a small detour results from the edge weights defined in formula 1. The green path from NF1 crossing the table is illustrated in b) compared with the red path containing navigation strategies of the guide-person"; Equations (1)-(3); Section IV. Path Planning - A. Graph Creation: "Edges connecting nodes from different layers are allowed. However, they will suffer from a multiplied penalty factor αl on the base of the initial edge weights. This, again, makes graph layer changes rare, although not impossible. Altogether, the path calculated by A is a compromise between the shortest distance way from A to B and an imitation of human behavior which the robot watches during the Home-Tour. Thus, the edge weight ω(Ni,Nj) between two nodes Ni,Nj is defined as follows:…"; Section V. Experiments: "The route of the guide-person began from A, via B, C, D, and ended in proximity to the start position A. The region between A and D corresponds to the corridor of the real environment … The path for the robot to the goal is computed using the approach described in section IV-A and illustrated in Fig. 8(a)."; Conclusion, all).
Although it is implied, Fang does not explicitly teach decide the movement target position of the mobile body based on a position corresponding to a point on the first edge or the one or more edges located in the moving direction of the person with respect to the first edge.
Horiuchi teaches wherein the one or more processors execute the instructions to decide the movement target position of the mobile body based on a position corresponding to a point on the first edge or the one or more edges located in the moving direction of the person with respect to the first edge (see Fig. 1, goal position 32 and/or goal route 52; [0076]-[0078 "After a determination is made that the tracking target 20 travels along route B, the goal position 32, the goal posture 42 and the goal route 52 are changed from the goal position 31, the goal posture 41 and the goal route 51 shown in FIG. 1 (1), respectively, and updated, as illustrated in FIG. 1 (2). In this case, a range of viewing angle (θ) includes only route B that is a selected route of the tracking target 20."] and [0083]).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to modify the system of Fang to decide the movement target position of the mobile body based on a position corresponding to a point on the first edge or the one or more edges located in the moving direction of the person with respect to the first edge, as taught by Horiuchi, in order to efficiently follow and track the person with an optimal posture to avoid losing sight of the person.
Regarding Claim 3
Modified Fang teaches the system according to claim 1 (as discussed above in claim 1),
Fang further teaches wherein the one or more processors execute the instructions to decide the movement target position of the mobile body based on a plurality of edges connected to the first edge at a first node among nodes to which the first edge is connected (see Fig. 8, all, especially "Note that the path with a small detour results from the edge weights defined in formula 1. The green path from NF1 crossing the table is illustrated in b) compared with the red path containing navigation strategies of the guide-person"; Equations (1)-(3); Section IV. Path Planning - A. Graph Creation: "Edges connecting nodes from different layers are allowed. However, they will suffer from a multiplied penalty factor αl on the base of the initial edge weights. This, again, makes graph layer changes rare, although not impossible. Altogether, the path calculated by A is a compromise between the shortest distance way from A to B and an imitation of human behavior which the robot watches during the Home-Tour. Thus, the edge weight ω(Ni,Nj) between two nodes Ni,Nj is defined as follows:…"; Section V. Experiments: "The route of the guide-person began from A, via B, C, D, and ended in proximity to the start position A. The region between A and D corresponds to the corridor of the real environment … The path for the robot to the goal is computed using the approach described in section IV-A and illustrated in Fig. 8(a)."; Conclusion, all).
Although it is implied, Fang does not explicitly teach decide the movement target position of the mobile body based on a plurality of edges connected to the first edge at a first node located in the moving direction of the person.
Horiuchi teaches wherein the one or more processors execute the instructions to decide the movement target position of the mobile body based on the first edge at a first node located in the moving direction of the person (see Fig. 1, goal position 32 and/or goal route 52; [0076]-[0078 "After a determination is made that the tracking target 20 travels along route B, the goal position 32, the goal posture 42 and the goal route 52 are changed from the goal position 31, the goal posture 41 and the goal route 51 shown in FIG. 1 (1), respectively, and updated, as illustrated in FIG. 1 (2). In this case, a range of viewing angle (θ) includes only route B that is a selected route of the tracking target 20."] and [0083]).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to modify the system of Fang to decide the movement target position of the mobile body based on a plurality of edges connected to the first edge at a first node located in the moving direction of the person, as taught by Horiuchi, in order to efficiently follow and track the person with an optimal posture to avoid losing sight of the person.
Regarding Claim 5
Modified Fang teaches the system according to claim 1 (as discussed above in claim 1),
Fang further teaches wherein the one or more processors execute the instructions to decide the movement target position in such a way that the mobile body leads or follows the person (see Fig. 2, "person following"; Section V. Experiments: "The both doors D1 and D2 were opened, while the robot was following the guide-person.").
Horiuchi additionally teaches wherein the one or more processors execute the instructions to decide the movement target position in such a way that the mobile body leads or follows the person (see Fig. 1, all; [0018 "...wherein the control parameter determination unit calculates a goal position for bringing the tracking target within a viewing angle of the mobile device and a goal posture at the goal position, and generates a control parameter including the calculated goal position and goal posture when one of a plurality of routes constituting a fork which the tracking target selects and moves along cannot be discriminated."] and [0077]-[0078 "After a determination is made that the tracking target 20 travels along route B, the goal position 32, the goal posture 42 and the goal route 52 are changed from the goal position 31, the goal posture 41 and the goal route 51 shown in FIG. 1 (1), respectively, and updated, as illustrated in FIG. 1 (2). In this case, a range of viewing angle (θ) includes only route B that is a selected route of the tracking target 20."]).
Regarding Claim 7
Modified Fang teaches the system according to claim 1 (as discussed above in claim 1),
Fang further teaches wherein the one or more processors execute the instructions to update the graph to offset an edge based on a determination that an obstacle is present on the edge (see Figs. 5 and 9, all; Section IV. Path Planning - B. Replanning: all, especially " If the percentage of occupied cells in this area exceeds a threshold, the object obstructing the current plan is confirmed and replanning is triggered."; Section V. Experiments: "Afterwards the robot tried to reach the subgoals on the way which the guide-person had passed by to C, i.e. the red path illustrated in Fig. 9(a). However, the door D1 lying on the robot path was closed purposely. Once the local approach ND was not successful and the robot was aware of the new obstacle D1 in front which obstructed the path, as discussed in section IV-B, replanning was started. The replanned path computed from the graph and the closed door D1 added into the map are shown in Fig. 9(b). Note that the uncertain (gray) regions between the both doors are relatively certain (white) now, compared with Fig. 6, since the robot has passed by this area again.").
Regarding Claim 8
Modified Fang teaches the system according to claim 1 (as discussed above in claim 1),
Fang further teaches wherein the one or more processors execute the instructions to update the graph to correct an edge in a manner dependent on a size of an obstacle present on the edge based on a determination that the obstacle is present on the edge (see Figs. 5 and 9, all; Section IV. Path Planning - B. Replanning: all, especially "For this purpose, grid cells contained in an ellipse covering the area between the robot and the subgoal are inspected, as Fig. 5 illustrates. If the percentage of occupied cells in this area exceeds a threshold, the object obstructing the current plan is confirmed and replanning is triggered. Considering the failure of ND and the detected obstacle between the robot and the next subgoal, this subgoal is marked as an unreachable node Nur.."; Section V. Experiments: "Once the local approach ND was not successful and the robot was aware of the new obstacle D1 in front which obstructed the path, as discussed in section IV-B, replanning was started. The replanned path computed from the graph and the closed door D1 added into the map are shown in Fig. 9(b).").
Regarding Claim 13
Modified Fang teaches the system according to claim 1 (as discussed above in claim 1),
Fang further teaches wherein the system is installed in a mobile body, the system further comprising:
a sensor (see Fig. 2, sensor readings; Section III. Robot Setup and Scenario: "The user who is interacting with the robot is tracked with a multi-modal person detection and tracking system from our previous work [15] combining the camera (face detection), laser (legs detection) and microphone data (sound location), and providing person positions in polar coordinate system with respect to the robot.");
a controller configured to control a movement of the mobile body to move toward the movement target position (see Figs. 8-10, all; Section V. Experiments: "The path for the robot to the goal is computed using the approach described in section IV-A and illustrated in Fig. 8(a)."; the claimed "controller" is inherent); and
a driving unit configured to move the mobile body in accordance with the control by the controller (see Fig. 2, actuators),
wherein the one or more processors execute the instructions to estimate the position of the person based on an output from the sensor (see Section III. Robot Setup and Scenario: "The user who is interacting with the robot is tracked with a multi-modal person detection and tracking system from our previous work [15] combining the camera (face detection), laser (legs detection) and microphone data (sound location), and providing person positions in polar coordinate system with respect to the robot."; Section V. Experiments: "The path for the robot to the goal is computed using the approach described in section IV-A and illustrated in Fig. 8(a)."; the claimed "processor(s)" is inherent).
Horiuchi additionally teaches wherein the system is installed in a mobile body, the system further comprising:
a sensor (see [0018] and [0070 "That is, the viewing angle (θ) 61 corresponds to an object recognition range of a sensor such as a camera included in the robot 10."]);
a controller configured to control a movement of the mobile body to move toward the movement target position (see Fig. 23, all; [0018] and [0089]); and
a driving unit configured to move the mobile body in accordance with the control by the controller (see [0018] and [0119 "The robot drive unit 132 drives the mobile device (robot) 100 according to the drive information input from the robot drive information generation unit 131. As a result, the mobile device (robot) 100 reaches the goal position via the goal route, and is set in the goal posture at the goal position."]),
wherein the one or more processors execute the instructions to estimate the position of the person based on an output from the sensor (see Fig. 23, all; [0018] and [0064]-[0083]).
Regarding Claim 14
Modified Fang teaches the system according to claim 13 (as discussed above in claim 13),
Fang further teaches wherein the controller is configured to control the mobile body in such a way that the mobile body moves on a route indicated by the edge in response to a determination that an obstacle is present between a current position of the mobile body and the movement target position (see Figs. 5 and 9, all, especially "Comparison of the planned and replanned path. a) shows the planned path on the base of the built map during the Home-Tour. Tuning edge weights defined in formula 1 the blue dashed shortcut would be an alternative neglecting potential obstacles in the region shown by the green arrow. Once the new obstacle D1 had been added in the grid map and detected by the robot, replanning was started. The resulting path is illustrated in b)."; Section IV. Path Planning - B. Replanning: all, especially " If the percentage of occupied cells in this area exceeds a threshold, the object obstructing the current plan is confirmed and replanning is triggered."; Section V. Experiments: "Afterwards the robot tried to reach the subgoals on the way which the guide-person had passed by to C, i.e. the red path illustrated in Fig. 9(a). However, the door D1 lying on the robot path was closed purposely. Once the local approach ND was not successful and the robot was aware of the new obstacle D1 in front which obstructed the path, as discussed in section IV-B, replanning was started. The replanned path computed from the graph and the closed door D1 added into the map are shown in Fig. 9(b). Note that the uncertain (gray) regions between the both doors are relatively certain (white) now, compared with Fig. 6, since the robot has passed by this area again.").
Regarding Claim 15
Modified Fang teaches the system according to claim 13 (as discussed above in claim 13),
Fang further teaches wherein the controller is configured to control the mobile body in such a manner that the mobile body moves straight from the current position of the mobile body to the movement target position in response to a determination that no obstacle is present between the current position of the mobile body and the movement target position (see Fig. 9, blue dashed shortcut, "Comparison of the planned and replanned path. a) shows the planned path on the base of the built map during the Home-Tour. Tuning edge weights defined in formula 1 the blue dashed shortcut would be an alternative neglecting potential obstacles in the region shown by the green arrow."; Section V. Experiments: "In principle, tuning edge weights defined in formula 1 a shortcut depicted with blue dashed in Fig. 9(a) is possible.").
Regarding Claim 17
Fang teaches a method of controlling a mobile body to move in accordance with movement of a person (see all Figs.; Abstract, all), the method comprising:
acquiring information indicating a position and a moving direction of a person (see Section III. Robot Setup and Scenario: "The user who is interacting with the robot is tracked with a multi-modal person detection and tracking system from our previous work [15] combining the camera (face detection), laser (legs detection) and microphone data (sound location), and providing person positions in polar coordinate system with respect to the robot. During the Home-Tour the human movement containing navigation strategies of the guide-person is observed by the robot. All of the person positions obtaining from the tracking system are recorded to build a graph with multiple layers, as will be elaborated on in section IV-A."; Section IV. Path Planning - A. Graph Creation: "The person tracking system provides dense information about person positions calculated in the world frame, namely the occupancy grid map of the environment created by the SLAM component ... Hence, the person positions are inserted as nodes Ni into a graph GNoEdge without connections between the nodes. The creation of edges in the graph will be discussed later on in this section. Considering that during the Home-Tour introduced in section III different locations are shown to the robot one after another, the whole human trajectory (all of the person positions) is segmented into sub-trajectories, where each sub-trajectory illustrates the set of person positions beginning at location A and ending at the subsequent location B shown by the guide-person. In particular the first sub trajectory records the person positions from the beginning of the scenario to the first location, while the last one stores the person trajectory from the last location to the end of the guided tour.");
acquiring a graph that includes nodes and edges and indicates a movement route of the person (see Fig. 4, all; Fig. 5, all; Figs. 7-8, all; Section IV. Path Planning - A. Graph Creation: "Hence, the person positions are inserted as nodes Ni into a graph GNoEdge without connections between the nodes … Therefore, each node Ni of the graph GNoEdge can be assigned to a corresponding layer GLayer(Ni)3, and all nodes belonging to a graph layer GLayer represent a sub-trajectory of the guide-person. A virtual grid with a predefined resolution different from the resolution of the occupancy grid map is laid over the built map, and the number of nodes is limited to one per virtual grid cell. The connection of graph nodes is created simply under the restriction of distance. Newly added nodes get connected by an edge to all neighbor nodes whose grid cell distance is smaller than a certain threshold. By this means, nodes lying on different graph layers might be connected, suppose they are nearby each other; while there might be no edge between nodes on the same layer, when they are far from each other."; Section V. Experiments: "Notice that edges connecting nodes from different layers are allowed to realize layer switches, when the sub-trajectories of the person interweave each other.");
determining a first edge of the graph corresponding to the position of the person based on the position of the person (see Figs. 7-8, all, especially "Note that the path with a small detour results from the edge weights defined in formula 1. The green path from NF1 crossing the table is illustrated in b) compared with the red path containing navigation strategies of the guide-person"; Equations (1)-(3); Section IV. Path Planning - A. Graph Creation: "Edges connecting nodes from different layers are allowed. However, they will suffer from a multiplied penalty factor αl on the base of the initial edge weights. This, again, makes graph layer changes rare, although not impossible. Altogether, the path calculated by A is a compromise between the shortest distance way from A to B and an imitation of human behavior which the robot watches during the Home-Tour. Thus, the edge weight ω(Ni,Nj) between two nodes Ni,Nj is defined as follows:…"; Section V. Experiments: "The route of the guide-person began from A, via B, C, D, and ended in proximity to the start position A. The region between A and D corresponds to the corridor of the real environment … The path for the robot to the goal is computed using the approach described in section IV-A and illustrated in Fig. 8(a)."); and
deciding a movement target position of the mobile body based on the first edge or on one or more edges (see Fig. 8, all, especially "Note that the path with a small detour results from the edge weights defined in formula 1. The green path from NF1 crossing the table is illustrated in b) compared with the red path containing navigation strategies of the guide-person"; Equations (1)-(3); Section IV. Path Planning - A. Graph Creation: "Edges connecting nodes from different layers are allowed. However, they will suffer from a multiplied penalty factor αl on the base of the initial edge weights. This, again, makes graph layer changes rare, although not impossible. Altogether, the path calculated by A is a compromise between the shortest distance way from A to B and an imitation of human behavior which the robot watches during the Home-Tour. Thus, the edge weight ω(Ni,Nj) between two nodes Ni,Nj is defined as follows:…"; Section V. Experiments: "The route of the guide-person began from A, via B, C, D, and ended in proximity to the start position A. The region between A and D corresponds to the corridor of the real environment … The path for the robot to the goal is computed using the approach described in section IV-A and illustrated in Fig. 8(a)."; Conclusion, all).
Although it is implied, Fang does not explicitly teach deciding a movement target position of the mobile body based on the first edge or on one or more edges located in the moving direction of the person with respect to the first edge.
Horiuchi teaches a method of controlling a mobile body to move in accordance with movement of a person (see all Figs., especially Fig. 1; [0001] and [0018]), the method comprising:
acquiring information indicating a position and a moving direction of a person (see Fig. 1 all; [0018] and [0064]-[0083], especially [0076 "The state at time t2 is a state after a determination is made that the tracking target 20 travels along route B between the two routes A and B that form the fork.']-[0077 "Analysis of a selected route of the tracking target 20 is performed, for example, by analyzing a direction or traveling direction of the tracking target from a camera-captured image of the robot 10."]);
acquiring a graph that includes a node and edges and indicates a movement route of the person (see Fig. 1 all; [0018] and [0064]-[0083], especially [0068 "In this time t1, the robot 10 cannot estimate or determine which of two routes forming a fork, route A and route B, along which the tracking target 20 will travel."], [0071 "That is, when the robot 10 is set in the goal posture 41 at the goal position 31, it is possible to bring the tracking target 20 within the field of view regardless of one of the two routes including route A or route B along which the tracking target 20 travels, and it is possible to continue the tracking processing without losing sight of the tracking target 20."] and [0076 "The state at time t2 is a state after a determination is made that the tracking target 20 travels along route B between the two routes A and B that form the fork."]);
determining a first edge of the graph corresponding to the position of the person based on the position of the person (see Fig. 1, route B; [0076 "The state at time t2 is a state after a determination is made that the tracking target 20 travels along route B between the two routes A and B that form the fork."] and [0077]-[0078 "After a determination is made that the tracking target 20 travels along route B,..."]); and
deciding a movement target position of the mobile body based on the first edge or on one or more edges located in the moving direction of the person with respect to the first edge (see Fig. 1, goal position 32 and/or goal route 52; [0076]-[0078 "After a determination is made that the tracking target 20 travels along route B, the goal position 32, the goal posture 42 and the goal route 52 are changed from the goal position 31, the goal posture 41 and the goal route 51 shown in FIG. 1 (1), respectively, and updated, as illustrated in FIG. 1 (2). In this case, a range of viewing angle (θ) includes only route B that is a selected route of the tracking target 20."] and [0083]).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to modify the process of Fang to include a step to decide a movement target position of the mobile body based on the first edge or on one or more edges located in the moving direction of the person with respect to the first edge, as taught by Horiuchi, in order to efficiently follow and track the person with an optimal posture to avoid losing sight of the person.
Regarding Claim 18
Fang teaches a non-transitory computer-readable medium storing a program executable by a computer to perform a method of controlling a mobile body to move in accordance with movement of a person (see all Figs., especially 2, 8 and 10; Abstract, all), the method comprising:
acquiring information indicating a position and a moving direction of a person (see Section III. Robot Setup and Scenario: "The user who is interacting with the robot is tracked with a multi-modal person detection and tracking system from our previous work [15] combining the camera (face detection), laser (legs detection) and microphone data (sound location), and providing person positions in polar coordinate system with respect to the robot. During the Home-Tour the human movement containing navigation strategies of the guide-person is observed by the robot. All of the person positions obtaining from the tracking system are recorded to build a graph with multiple layers, as will be elaborated on in section IV-A."; Section IV. Path Planning - A. Graph Creation: "The person tracking system provides dense information about person positions calculated in the world frame, namely the occupancy grid map of the environment created by the SLAM component ... Hence, the person positions are inserted as nodes Ni into a graph GNoEdge without connections between the nodes. The creation of edges in the graph will be discussed later on in this section. Considering that during the Home-Tour introduced in section III different locations are shown to the robot one after another, the whole human trajectory (all of the person positions) is segmented into sub-trajectories, where each sub-trajectory illustrates the set of person positions beginning at location A and ending at the subsequent location B shown by the guide-person. In particular the first sub trajectory records the person positions from the beginning of the scenario to the first location, while the last one stores the person trajectory from the last location to the end of the guided tour.");
acquiring a graph that includes nodes and edges and indicates a movement route of the person (see Fig. 4, all; Fig. 5, all; Figs. 7-8, all; Section IV. Path Planning - A. Graph Creation: "Hence, the person positions are inserted as nodes Ni into a graph GNoEdge without connections between the nodes … Therefore, each node Ni of the graph GNoEdge can be assigned to a corresponding layer GLayer(Ni)3, and all nodes belonging to a graph layer GLayer represent a sub-trajectory of the guide-person. A virtual grid with a predefined resolution different from the resolution of the occupancy grid map is laid over the built map, and the number of nodes is limited to one per virtual grid cell. The connection of graph nodes is created simply under the restriction of distance. Newly added nodes get connected by an edge to all neighbor nodes whose grid cell distance is smaller than a certain threshold. By this means, nodes lying on different graph layers might be connected, suppose they are nearby each other; while there might be no edge between nodes on the same layer, when they are far from each other."; Section V. Experiments: "Notice that edges connecting nodes from different layers are allowed to realize layer switches, when the sub-trajectories of the person interweave each other.");
determining a first edge of the graph corresponding to the position of the person based on the position of the person (see Figs. 7-8, all, especially "Note that the path with a small detour results from the edge weights defined in formula 1. The green path from NF1 crossing the table is illustrated in b) compared with the red path containing navigation strategies of the guide-person"; Equations (1)-(3); Section IV. Path Planning - A. Graph Creation: "Edges connecting nodes from different layers are allowed. However, they will suffer from a multiplied penalty factor αl on the base of the initial edge weights. This, again, makes graph layer changes rare, although not impossible. Altogether, the path calculated by A is a compromise between the shortest distance way from A to B and an imitation of human behavior which the robot watches during the Home-Tour. Thus, the edge weight ω(Ni,Nj) between two nodes Ni,Nj is defined as follows:…"; Section V. Experiments: "The route of the guide-person began from A, via B, C, D, and ended in proximity to the start position A. The region between A and D corresponds to the corridor of the real environment … The path for the robot to the goal is computed using the approach described in section IV-A and illustrated in Fig. 8(a)."); and
deciding a movement target position of the mobile body based on the first edge or on one or more edges (see Fig. 8, all, especially "Note that the path with a small detour results from the edge weights defined in formula 1. The green path from NF1 crossing the table is illustrated in b) compared with the red path containing navigation strategies of the guide-person"; Equations (1)-(3); Section IV. Path Planning - A. Graph Creation: "Edges connecting nodes from different layers are allowed. However, they will suffer from a multiplied penalty factor αl on the base of the initial edge weights. This, again, makes graph layer changes rare, although not impossible. Altogether, the path calculated by A is a compromise between the shortest distance way from A to B and an imitation of human behavior which the robot watches during the Home-Tour. Thus, the edge weight ω(Ni,Nj) between two nodes Ni,Nj is defined as follows:…"; Section V. Experiments: "The route of the guide-person began from A, via B, C, D, and ended in proximity to the start position A. The region between A and D corresponds to the corridor of the real environment … The path for the robot to the goal is computed using the approach described in section IV-A and illustrated in Fig. 8(a)."; Conclusion, all).
Although it is implied, Fang does not explicitly teach deciding a movement target position of the mobile body based on the first edge or on one or more edges located in the moving direction of the person with respect to the first edge.
Horiuchi teaches a non-transitory computer-readable medium storing a program executable by a computer to perform a method of controlling a mobile body to move in accordance with movement of a person (see all Figs., especially Fig. 1 and Fig. 23, memory 508 and data processing unit 503; [0001] and [0018]), the method comprising:
acquiring information indicating a position and a moving direction of a person (see Fig. 1 all; [0018] and [0064]-[0083], especially [0076 "The state at time t2 is a state after a determination is made that the tracking target 20 travels along route B between the two routes A and B that form the fork.']-[0077 "Analysis of a selected route of the tracking target 20 is performed, for example, by analyzing a direction or traveling direction of the tracking target from a camera-captured image of the robot 10."]);
acquiring a graph that includes a node and edges and indicates a movement route of the person (see Fig. 1 all; [0018] and [0064]-[0083], especially [0068 "In this time t1, the robot 10 cannot estimate or determine which of two routes forming a fork, route A and route B, along which the tracking target 20 will travel."], [0071 "That is, when the robot 10 is set in the goal posture 41 at the goal position 31, it is possible to bring the tracking target 20 within the field of view regardless of one of the two routes including route A or route B along which the tracking target 20 travels, and it is possible to continue the tracking processing without losing sight of the tracking target 20."] and [0076 "The state at time t2 is a state after a determination is made that the tracking target 20 travels along route B between the two routes A and B that form the fork."]);
determining a first edge of the graph corresponding to the position of the person based on the position of the person (see Fig. 1, route B; [0076 "The state at time t2 is a state after a determination is made that the tracking target 20 travels along route B between the two routes A and B that form the fork."] and [0077]-[0078 "After a determination is made that the tracking target 20 travels along route B,..."]); and
deciding a movement target position of the mobile body based on the first edge or on one or more edges located in the moving direction of the person with respect to the first edge (see Fig. 1, goal position 32 and/or goal route 52; [0076]-[0078 "After a determination is made that the tracking target 20 travels along route B, the goal position 32, the goal posture 42 and the goal route 52 are changed from the goal position 31, the goal posture 41 and the goal route 51 shown in FIG. 1 (1), respectively, and updated, as illustrated in FIG. 1 (2). In this case, a range of viewing angle (θ) includes only route B that is a selected route of the tracking target 20."] and [0083]).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to modify the non-transitory computer-readable medium of Fang to include instructions to decide a movement target position of the mobile body based on the first edge or on one or more edges located in the moving direction of the person with respect to the first edge, as taught by Horiuchi, in order to efficiently follow and track the person with an optimal posture to avoid losing sight of the person.
Claim 4 is rejected under 35 U.S.C. 103 as being unpatentable over Fang (as modified by Horiuchi) as applied to claim 3 above, and further in view of NPL_Ardiyanto - "Human Motion Prediction..." (Ardiyanto hereinafter).
Regarding Claim 4
Modified Fang teaches the system according to claim 3 (as discussed above in claim 3),
Fang further teaches decide, as the movement target position of the mobile body, a position on a route obtained (see Fig. 8, all, especially "Note that the path with a small detour results from the edge weights defined in formula 1. The green path from NF1 crossing the table is illustrated in b) compared with the red path containing navigation strategies of the guide-person"; Equations (1)-(3); Section IV. Path Planning - A. Graph Creation: "Edges connecting nodes from different layers are allowed. However, they will suffer from a multiplied penalty factor αl on the base of the initial edge weights. This, again, makes graph layer changes rare, although not impossible. Altogether, the path calculated by A is a compromise between the shortest distance way from A to B and an imitation of human behavior which the robot watches during the Home-Tour. Thus, the edge weight ω(Ni,Nj) between two nodes Ni,Nj is defined as follows:…"; Section V. Experiments: "The route of the guide-person began from A, via B, C, D, and ended in proximity to the start position A. The region between A and D corresponds to the corridor of the real environment … The path for the robot to the goal is computed using the approach described in section IV-A and illustrated in Fig. 8(a)."; Conclusion, all).
Fang is silent regarding wherein the one or more processors execute the instructions to evaluate probabilities that the person passes through routes corresponding to each of the plurality of edges connected to the first edge, and
decide a position on a route obtained by weighting and combining the routes corresponding to each of the plurality of edges in accordance with the probabilities.
Horiuchi teaches decide, as the movement target position of the mobile body, a position on a route obtained (see Fig. 1, goal position 32 and/or goal route 52; [0076]-[0078 "After a determination is made that the tracking target 20 travels along route B, the goal position 32, the goal posture 42 and the goal route 52 are changed from the goal position 31, the goal posture 41 and the goal route 51 shown in FIG. 1 (1), respectively, and updated, as illustrated in FIG. 1 (2). In this case, a range of viewing angle (θ) includes only route B that is a selected route of the tracking target 20."] and [0083]).
Ardiyanto teaches a system configured to control a mobile body to move in accordance with movement of a person (see Abstract, all), the system comprising:
one or more memories storing instructions; and one or more processors that execute the instructions to:
acquire information indicating a position and a moving direction of a person (see Section 3.1 Dataset Evaluations : "At first, we collect a set of person trajectories on five different locations/junctions at our campus (see Fig. 4), using a laser-based person tracker [11]."; Section 3.2 Predicting the human motion on a robot: "We employ a mobile robot equipped by a laser range finder and a camera to verify the performance of our human motion prediction. The same laser-based per son tracker mentioned in section 3.1 is utilized. We carry out the experiments on “location 1”.");
acquire a graph that includes nodes and edges and indicates a movement route of the person (see Figs. 2, 4 and 5, all; Section 2.1 Environment representation as a graph: "Now, we are able to represent the map as a graph which connects the hallway and junction nodes, as shown in Fig. 2. We set the range area of each node to 10 meters, assuming the robot ability to detect and track the person is limited (i.e. the robot visibility, denoted by V). Here, the environmental context reasoning are employed. We assume the human motion on the hallway nodes can be classified into two classes, getting close and going away. Regardless of the junction node, we also presume the human motion will follow the skeleton shape."); and
determine a first edge of the graph corresponding to the position of the person based on the position of the person (see Figs. 2 and 5-6, all; Section 2.1 Environment representation as a graph, all; Section 3.2 Predicting the human motion on a robot: "We employ a mobile robot equipped by a laser range finder and a camera to verify the performance of our human motion prediction. The same laser-based person tracker mentioned in section 3.1 is utilized. We carry out the experiments on “location 1”. Figure 5 shows the prediction performance of our system. Initially, each possible trajectory of the per on towards the predicted goal has an equal distribution. The predicted goals are determined by the current frontiers of the robot, explained in section 2.1. As the person data sequence grows, the information about the person speed, orientation, and the environmental context becomes more certain and will be fed to our system. Hereupon, the predicted trajectory will be condensed towards the predicted goals which have a higher likelihood according to the classifier.");
wherein the one or more processors execute the instructions to evaluate probabilities that the person passes through routes corresponding to each of the plurality of edges connected to the first edge (see Figs. 5-6, all: Abstract, all; Section 2.2.3 Particle filter-based predictor: "We now have the confidence of the possible person intention to head up to each goal in G using the score of U. The last step is to generate the possible trajectory of the person by connecting each goal to the current person pose using a bezier curve considering its confidence (e.g. Fig. 1). Please notice that the decision of choosing the goal can be determined when the confidence is above a threshold; Section 3.2 Predicting the human motion on a robot: "Figure 5 shows the prediction performance of our system. Initially, each possible trajectory of the person towards the predicted goal has an equal distribution. The predicted goals are determined by the current frontiers of the robot, explained in section 2.1. As the person data sequence grows, the information about the person speed, orientation, and the environmental context becomes more certain and will be fed to our system. Hereupon, the predicted trajectory will be condensed towards the predicted goals which have a higher likelihood according to the classifier."; Conclusion, all), and decide a position on a route obtained by weighting and combining the routes corresponding to each of the plurality of edges in accordance with the probabilities (see Figs. 5-6, all: Section 2.2.3 Particle filter-based predictor: "We now have the confidence of the possible person intention to head up to each goal in G using the score of U. The last step is to generate the possible trajectory of the person by connecting each goal to the current person pose using a bezier curve considering its confidence (e.g. Fig. 1). Please notice that the decision of choosing the goal can be determined when the confidence is above a threshold; Section 3.2 Predicting the human motion on a robot: "Figure 5 shows the prediction performance of our system. Initially, each possible trajectory of the person towards the predicted goal has an equal distribution. The predicted goals are determined by the current frontiers of the robot, explained in section 2.1. As the person data sequence grows, the information about the person speed, orientation, and the environmental context becomes more certain and will be fed to our system. Hereupon, the predicted trajectory will be condensed towards the predicted goals which have a higher likelihood according to the classifier.").
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to further modify the system of modified Fang to evaluate probabilities that the person passes through routes corresponding to each of the plurality of edges connected to the first edge and decide a position on a route obtained by weighting and combining the routes corresponding to each of the plurality of edges in accordance with the probabilities, as taught by Ardiyanto, in order to accurately predict the persons movement at a junction such as a hallway indoors or an intersection on a road.
Claims 6 and 9 are rejected under 35 U.S.C. 103 as being unpatentable over Fang (as modified by Horiuchi) as applied to claims 1 and 8 above, and further in view of Hong (US 20180051991 A1 and Hong hereinafter).
Regarding Claim 6
Modified Fang teaches the system according to claim 1 (as discussed above in claim 1),
Fang further teaches wherein the one or more processors execute the instructions to update the graph to offset an edge based on a determination that an obstacle is present on the edge (see Figs. 5 and 9, all; Section IV. Path Planning - B. Replanning: all, especially " If the percentage of occupied cells in this area exceeds a threshold, the object obstructing the current plan is confirmed and replanning is triggered."; Section V. Experiments: "Afterwards the robot tried to reach the subgoals on the way which the guide-person had passed by to C, i.e. the red path illustrated in Fig. 9(a). However, the door D1 lying on the robot path was closed purposely. Once the local approach ND was not successful and the robot was aware of the new obstacle D1 in front which obstructed the path, as discussed in section IV-B, replanning was started. The replanned path computed from the graph and the closed door D1 added into the map are shown in Fig. 9(b). Note that the uncertain (gray) regions between the both doors are relatively certain (white) now, compared with Fig. 6, since the robot has passed by this area again.")
Although it is implied, Fang does not explicitly teach update the graph to delete an edge.
Hong teaches a system configured to control a mobile body to move (see all Figs.; [0004]), the system comprising:
one or more memories storing instructions; and one or more processors (see [0004]) that execute the instructions to:
acquire a graph that includes nodes and edges (see most Figs., especially Figs. 4, 7 and 9; [0017] and [0033 "At 52 of method 48, path-finding system 16 may create a navigation graph of environment 18 by dividing the environment into grid cells, generating a navigation node at the center of each unoccupied grid cell, and constructing edges that connect adjacent nodes with no obstacle in between."]); and
decide a movement target position of the mobile body based on the first edge or on one or more edges (see [0004], [0033 "The initial position of vehicle 10 is represented by a beginning node B, and the goal is represented by goal node G. The shaded area represents obstacle 24. In the subsequent path-search phase, the path finding system discovers an optimal path from B to G, which avoids the obstacle."]);
wherein the one or more processors execute the instructions to update the graph to delete an edge based on a determination that an obstacle is present on the edge (see Figs. 7A-7C, all; Figs. 9A-9C, all; [0033], [0037 "If the neighbor node is not obstacle-free, then at 84 the neighbor node is deleted. If the neighbor node is obstacle free, then it is determined at 86 whether the edge between the neighbor node N and node S is obstacle-free. If the edge is not obstacle-free then, at 88, the edge is deleted."]-[0038 "In the Lazy A* PPA, nodes and edges are initially generated in the graph-construction phase, regardless of obstacles, as shown in FIG. 7A. However, navigation nodes and edges are evaluated in the path-search phase only if they are obstacle-free. If a node or an edge is not obstacle-free, then that node or edge is deleted from the navigation graph, as shown in FIGS. 7B and 7C, which represent subsequent stages of graph construction."] and [0042]).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to further modify the system of modified Fang to update the graph to delete an edge based on a determination that an obstacle is present on the edge, as taught by Hong, in order to remove unnecessary edges which would cause collision between the mobile body and the obstacle.
Regarding Claim 9
Modified Fang teaches the system according to claim 8 (as discussed above in claim 8),
Fang further teaches wherein the one or more processors execute the instructions to update the graph to offset the edge when a ratio of a length of a portion of the edge passing through a region of the obstacle to a length of the edge is larger than a threshold (see Figs. 5 and 9, all; Section IV. Path Planning - B. Replanning: all, especially "For this purpose, grid cells contained in an ellipse covering the area between the robot and the subgoal are inspected, as Fig. 5 illustrates. If the percentage of occupied cells in this area exceeds a threshold, the object obstructing the current plan is confirmed and replanning is triggered. Considering the failure of ND and the detected obstacle between the robot and the next subgoal, this subgoal is marked as an unreachable node Nur.."; Section V. Experiments: "Once the local approach ND was not successful and the robot was aware of the new obstacle D1 in front which obstructed the path, as discussed in section IV-B, replanning was started. The replanned path computed from the graph and the closed door D1 added into the map are shown in Fig. 9(b).").
Although it is implied, Fang does not explicitly teach update the graph to delete the edge.
Hong teaches wherein the one or more processors execute the instructions to update the graph to delete the edge when a portion of the edge passes through a region of the obstacle (see Figs. 7A-7C, all; Figs. 9A-9C, all; [0033], [0037 "If the neighbor node is not obstacle-free, then at 84 the neighbor node is deleted. If the neighbor node is obstacle free, then it is determined at 86 whether the edge between the neighbor node N and node S is obstacle-free. If the edge is not obstacle-free then, at 88, the edge is deleted."]-[0038 "In the Lazy A* PPA, nodes and edges are initially generated in the graph-construction phase, regardless of obstacles, as shown in FIG. 7A. However, navigation nodes and edges are evaluated in the path-search phase only if they are obstacle-free. If a node or an edge is not obstacle-free, then that node or edge is deleted from the navigation graph, as shown in FIGS. 7B and 7C, which represent subsequent stages of graph construction."] and [0042]).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to further modify the system of modified Fang to update the graph to delete the edge, as taught by Hong, in order to remove unnecessary edges which would cause collision between the mobile body and the obstacle.
Claim 10 is rejected under 35 U.S.C. 103 as being unpatentable over Fang (as modified by Horiuchi) as applied to claim 9 above, and further in view of Toebes (US 20160176638 A1 and Toebes hereinafter).
Regarding Claim 10
Modified Fang teaches the system according to claim 9 (as discussed above in claim 9),
Fang is silent regarding wherein the one or more processors execute the instructions to update the graph to offset the edge when the ratio of the length of the portion of the edge passing through the region of the obstacle to the length of the edge is equal to or smaller than the threshold.
Toebes teaches a system configured to control a mobile body to move (see all Figs.; [0024]), the system comprising:
one or more memories storing instructions; and one or more processors (see [0031] and [0037]) that execute the instructions to:
acquire a graph that includes edges (see Fig. 1A, selectable paths 75 and Fig. 8, path 16; [0027 "The automated guided vehicle 10 is configured, as will be described below, so that the undeterministic traverse service 30S, 70S provides holonomic selectable paths 75 for the automated guided vehicle substantially everywhere on the respective undeterministic traverse surfaces 30S, 70S."] and [0035 "A route marker 14 indicating an automated guided vehicle 10 path is employed in situations where either a line of sight between beacons does not exist or traveling in a straight path between beacons is not desired ... When placing the line to mark the automated guided vehicle 10 path, workers need not allow space between line and objects. Any time the automated guided vehicle 10 finds its path partially blocked by an object, the automated guided vehicle 10 will increase its offset from the line so that it can follow the line without colliding with the object."]); and
decide a movement target position of the mobile body based on the first edge or on one or more edges (see [0024], [0027 "The automated guided vehicle 10 is configured, as will be described below, so that the undeterministic traverse service 30S, 70S provides holonomic selectable paths 75 for the automated guided vehicle substantially everywhere on the respective undeterministic traverse surfaces 30S, 70S.”] and [0035]);
wherein the one or more processors execute the instructions to update the graph to offset the edge when the ratio of the length of the portion of the edge passing through the region of the obstacle to the length of the edge is equal to or smaller than the threshold (see [0035 "Any time the automated guided vehicle 10 finds its path partially blocked by an object, the automated guided vehicle 10 will increase its offset from the line so that it can follow the line without colliding with the object."]-[0037]).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to further modify the system of modified Fang to update the graph to offset the edge when the ratio of the length of the portion of the edge passing through the region of the obstacle to the length of the edge is equal to or smaller than the threshold, as taught by Toebes, in order to follow an edge depicted on the floor without colliding with the obstacle.
Claims 11-12 are rejected under 35 U.S.C. 103 as being unpatentable over Fang (as modified by Horiuchi) as applied to claim 1 above, and further in view of Jeon et al. (US 20240310846 A1 and Jeon hereinafter).
Regarding Claim 11
Modified Fang teaches the system according to claim 1 (as discussed above in claim 1),
Fang further teaches wherein the one or more processors execute the instructions to:
estimate a position of the mobile body based on an output from a sensor included in the mobile body, and generate an environment map in a coordinate system based on the mobile body as a reference (see Fig. 4, all; Fig. 5, all; Figs. 7-8, all; Section III. Robot Setup and Scenario: "The user who is interacting with the robot is tracked with a multi-modal person detection and tracking system from our previous work [15] combining the camera (face detection), laser (legs detection) and microphone data (sound location), and providing person positions in polar coordinate system with respect to the robot."; Section IV. Path Planning - A. Graph Creation: "The person tracking system provides dense information about person positions calculated in the world frame, namely the occupancy grid map of the environment created by the SLAM component ... Hence, the person positions are inserted as nodes Ni into a graph GNoEdge without connections between the nodes. The creation of edges in the graph will be discussed later on in this section. Considering that during the Home-Tour introduced in section III different locations are shown to the robot one after another, the whole human trajectory (all of the person positions) is segmented into sub-trajectories, where each sub-trajectory illustrates the set of person positions beginning at location A and ending at the subsequent location B shown by the guide-person. In particular the first sub trajectory records the person positions from the beginning of the scenario to the first location, while the last one stores the person trajectory from the last location to the end of the guided tour.").
Fang is silent regarding decide the movement target position of the mobile body based on the graph converted into the coordinate system based on the mobile body as the reference and aligned with the environment map.
Jeon teaches a system configured to control a mobile body to move (see all Figs.; [0007]), the system comprising:
one or more memories storing instructions; and one or more processors (see [0013] and [0054]) that execute the instructions to:
acquire a graph that includes nodes and edges (see Figs. 4-6, all; [0007 "In one general aspect, a processor-implemented method of a mobile computing apparatus includes generating a global path connecting a current position of the mobile computing apparatus with a future destination of the mobile computing apparatus based on a topology map that is generated based on mapping information ..."]-[0008 "The method may further include downloading the mapping information from a device that is external of the mobile computing apparatus, determining nodes corresponding to the plurality of waypoints and edges connecting the nodes with one another from the mapping information, and generating the topology map based on the nodes and the edges."] and [0010 "The mapping of the global path to the occupancy grid map may include converting coordinate values of a plurality of nodes of the global path into coordinate values in a coordinate system of the mobile computing apparatus."]); and
decide a movement target position of the mobile body based on the first edge or on one or more edges (see Fig. 7. all; [0007 "...mapping the global path to the occupancy grid map, generating a sub-waypoint located in the drivable area in response to a next waypoint, to which the mobile computing apparatus is set to travel based on the global path, being determined to correspond to the un-drivable area, where the next waypoint is among a plurality of waypoints included in the global path, and generating a local path, for a traveling of the mobile computing apparatus, connecting the current position with the sub-waypoint."] and [0017]);
wherein the one or more processors execute the instructions to:
estimate a position of the mobile body based on an output from a sensor included in the mobile body, and generate an environment map in a coordinate system based on the mobile body as a reference (see Fig. 8, all; [0007 "...generating, in real time, an occupancy grid map based on sensor data obtained from a sensor of the mobile computing apparatus, the occupancy grid map representing an un-drivable area and a drivable area in a surrounding environment of the mobile computing apparatus..."], [0058] and [0085 "FIG. 8 is a diagram illustrating a position of a waypoint marked or reflected in an occupancy grid map, e.g., in the coordinate system of the mobile computing apparatus, for example. The waypoint may have been first generated in a topology map according to various embodiments, and then mapped to the occupancy grid map."]); and
decide the movement target position of the mobile body based on the graph converted into the coordinate system based on the mobile body as the reference and aligned with the environment map (see [0007 "In one general aspect, a processor-implemented method of a mobile computing apparatus includes generating a global path connecting a current position of the mobile computing apparatus with a future destination of the mobile computing apparatus based on a topology map that is generated based on mapping information ... mapping the global path to the occupancy grid map, generating a sub-waypoint located in the drivable area in response to a next waypoint, to which the mobile computing apparatus is set to travel based on the global path, being determined to correspond to the un-drivable area, where the next waypoint is among a plurality of waypoints included in the global path, and generating a local path, for a traveling of the mobile computing apparatus, connecting the current position with the sub-waypoint."], [0010 "The mapping of the global path to the occupancy grid map may include converting coordinate values of a plurality of nodes of the global path into coordinate values in a coordinate system of the mobile computing apparatus."] and [0059 "In operation S140, the global path, generated in the topology map, may be mapped to the occupancy grid map based on a coordinate system of the mobile computing apparatus, e.g., from a perspective of the mobile computing apparatus. Such a mapping of the global path may denote a process of aligning the occupancy grid map in the topology map."]).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to further modify the system of modified Fang to decide the movement target position of the mobile body based on the graph converted into the coordinate system based on the mobile body as the reference and aligned with the environment map, as taught by Jeon, in order to generate a local path for the mobile body to follow in real-time.
Regarding Claim 12
Modified Fang teaches the system according to claim 11 (as discussed above in claim 11),
Fang is silent regarding wherein the one or more processors execute the instructions to transform the graph and align the graph with the environment map to alleviate a change in a conversion result of the graph caused by a change in the coordinate system based on the mobile body as the reference.
Jeon teaches wherein the one or more processors execute the instructions to transform the graph and align the graph with the environment map to alleviate a change in a conversion result of the graph caused by a change in the coordinate system based on the mobile body as the reference (see [0007 "...mapping the global path to the occupancy grid map, generating a sub-waypoint located in the drivable area in response to a next waypoint, to which the mobile computing apparatus is set to travel based on the global path, being determined to correspond to the un-drivable area, where the next waypoint is among a plurality of waypoints included in the global path, and generating a local path, for a traveling of the mobile computing apparatus, connecting the current position with the sub-waypoint."], [0010 "The mapping of the global path to the occupancy grid map may include converting coordinate values of a plurality of nodes of the global path into coordinate values in a coordinate system of the mobile computing apparatus."] and [0059 "In operation S140, the global path, generated in the topology map, may be mapped to the occupancy grid map based on a coordinate system of the mobile computing apparatus, e.g., from a perspective of the mobile computing apparatus. Such a mapping of the global path may denote a process of aligning the occupancy grid map in the topology map."]).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to further modify the system of modified Fang to transform the graph and align the graph with the environment map to alleviate a change in a conversion result of the graph caused by a change in the coordinate system based on the mobile body as the reference, as taught by Jeon, in order to generate a local path for the mobile body to follow in real-time.
Claim 16 is rejected under 35 U.S.C. 103 as being unpatentable over Fang (as modified by Horiuchi) as applied to claim 13 above, and further in view of Kagaya (JP 2020144591 A and Kagaya hereinafter).
Regarding Claim 16
Modified Fang teaches the system according to claim 13 (as discussed above in claim 13),
Fang further teaches wherein a node corresponding to a destination of the person is set in advance (see Fig. 4, all; Fig. 5, all; Figs. 7-8, all; Section IV. Path Planning - A. Graph Creation: "Hence, the person positions are inserted as nodes Ni into a graph GNoEdge without connections between the nodes … Therefore, each node Ni of the graph GNoEdge can be assigned to a corresponding layer GLayer(Ni)3, and all nodes belonging to a graph layer GLayer represent a sub-trajectory of the guide-person. A virtual grid with a predefined resolution different from the resolution of the occupancy grid map is laid over the built map, and the number of nodes is limited to one per virtual grid cell. The connection of graph nodes is created simply under the restriction of distance. Newly added nodes get connected by an edge to all neighbor nodes whose grid cell distance is smaller than a certain threshold. By this means, nodes lying on different graph layers might be connected, suppose they are nearby each other; while there might be no edge between nodes on the same layer, when they are far from each other."; Section V. Experiments: "Notice that edges connecting nodes from different layers are allowed to realize layer switches, when the sub-trajectories of the person interweave each other.").
Fang is silent regarding the controller is configured to change a relative position or an orientation of the mobile body with respect to the person at the movement target position in accordance with whether the person is located within a predetermined range from the node corresponding to the destination.
Kagaya teaches a system configured to control a mobile body to move in accordance with movement of a person (see all Figs.; [0009]; see the corresponding paragraphs in the attached reference JP_2020144591_A), the system comprising:
one or more memories storing instructions; and one or more processors (see [0010]) that execute the instructions to:
acquire information indicating a position and a moving direction of a person (see Figs. 4 and 6, all; [0009 "The moving body management device according to one aspect of the present disclosure includes a specific unit that specifies the traveling direction of the target person using images taken by the camera device, and a moving body that provides a service to the target person. "], [0040 "Next, the route search unit 104 sets the movement destination position P outside the traveling direction F of the target person 2 and the avoidance range 400."] and [0063]);
wherein a node corresponding to a destination of the person is set in advance (see Fig. 4, destination position P; Fig. 6, destination positions P1-P3; [0040 "Next, the route search unit 104 sets the movement destination position P outside the traveling direction F of the target person 2 and the avoidance range 400."] and [0063]), and
the controller is configured to change a relative position or an orientation of the mobile body with respect to the person at the movement target position in accordance with whether the person is located within a predetermined range from the node corresponding to the destination (see Figs. 4 and 6, all; [0040 "Next, the route search unit 104 sets the movement destination position P outside the traveling direction F of the target person 2 and the avoidance range 400. The movement destination position P may be set to a position along the boundary of the avoidance range 400 as shown in FIG. Alternatively, the movement destination position P may be set to a position away from the boundary of the avoidance range 400. Further, the moving destination position P may be set to any of the passages in the traveling direction F."] and [0041 "The route search unit 104 searches for the movement routes 401A, 401B, and 401C that arrive at the destination position while avoiding the passage of the avoidance range 400 for each of the robots 30A, 30B, and 30C. As a result, as shown in FIG. 4, the movement path 401X in which the robot 30C passes through the avoidance range 400 and arrives at the movement destination position P is not searched. That is, the movement path 401X in which the robot 30C approaches from the blind spot of the subject 2 is not searched. Therefore, it is possible to prevent the robot 30C from approaching the target person 2 from the blind spot and causing discomfort to the target person 2."]-[0049] and [0063]).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to further modify the system of modified Fang to change a relative position or orientation of the mobile body with respect to the person at the movement target position in accordance with whether the person is located within a predetermined range from the node corresponding to the destination, as taught by Kagaya, in order to approach the person at the destination in a friendly manner without causing discomfort to the person.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to TANNER LUKE CULLEN whose telephone number is (303)297-4384. The examiner can normally be reached Monday-Friday 9:00-5:00 MT.
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, Khoi Tran can be reached at (571) 272-6919. 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.
/TANNER L CULLEN/Examiner, Art Unit 3656 /KHOI H TRAN/Supervisory Patent Examiner, Art Unit 3656
Prosecution Insights