DETAILED ACTION
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claims 1-20 are pending.
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 1-20 are 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.
Claim 1 recites, at the last two subparagraphs:
selecting a tree node nearest to a target sampling point as a third tree node from a node set of the second exploration tree, and selecting a tree node on the first exploration tree nearest to the second exploration tree as a target tree node, wherein the target sampling point is obtained by extending sampling along the second tree node previously grown; and
in response to a minimum distance between the third tree node and the obstacle being not less than a preset distance threshold, growing a tree node as the second tree node according to a direction from the third tree node to the target sampling point and a direction from the third tree node to the target tree node.
It is not clear what “the target sampling point is obtained by extending sampling along the second tree node previously grown” means. It is not clear how a target sampling point is obtained, since a node is a point, and “along the second tree node” does not have a clear meaning.
It is not clear what is meant by “extending sampling”. This phrase seems to be referring to a previously introduced action of sampling, but the claims have not introduced any action of sampling. The claims have introduced a “target sampling point” but the claims have not introduced the action of sampling, and thus it is unclear what “extending sampling” means.
The above sub-paragraphs of claim 1 are describing the manner in which the second tree node is grown. “the target sampling point is obtained by extending sampling along the second tree node previously grown” requires the second tree node to have been previously grown. It is not clear how the second tree node can be grown based on the second tree node previously grown.
It is not clear what “growing a tree node as the second tree node according to a direction from the third tree node to the target sampling point and a direction from the third tree node to the target tree node” means. It is not clear how a node is grown as a second tree node according to two directions. Is growing a tree node as the second tree node generating a single “second tree node” based on the position of the tree node, or is this generating multiple “second tree nodes”?
Claims 12 and 13 contain similarly unclear language.
Claims 2-11 and 14-20 are rejected as being dependent on, and failing to cure the deficiencies of, rejected independent claim 1.
Claim 6, at lines 8-9, requires “randomly selecting the target sampling point along the second tree node previously grown.” It is not clear what “along the second tree node” means as a node is a point and does not have a direction associated with it.
Claim 7, lines 4-5; and claim 8, last two lines are similarly unclear.
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claims 1, 12, and 13 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Zhao et al. (CN 113934206A, citations are to the translation provided herewith.).
Zhao teaches,
Re claim 1. A path planning method, comprising:
acquiring a motion space, a starting position, and an end position of a moving object, and information of an obstacle ([0010]: “Create a line connecting the starting point and the target point, where the starting point and the target point are the first node and the second node, respectively.”; [0013]: “Optionally, when there is no obstacle at the midpoint of the connecting line, the third node is the midpoint of the connecting line; when there is an obstacle at the midpoint of the connecting line, the third node is a point on the connecting line that is close to the midpoint and has no obstacle.”);
constructing a first exploration tree starting from the starting position and constructing a second exploration tree starting from the end position in the motion space, wherein the first exploration tree and the second exploration tree grow toward each other according to the information of the obstacle ([0052]: “the bidirectional fast random search tree (RRT-Connect) algorithm makes two major improvements on the Rapidly exploring Random Trees (RRT) algorithm: it generates random trees from the starting and ending state points respectively, and the planning is completed when the two trees intersect, which greatly improves the search speed of the algorithm; it adopts a node greedy expansion strategy, in each iteration when generating nodes, the algorithm will try to use the nearest node of the other tree as the expansion direction of this tree, so that the two trees intersect quickly. Meanwhile, when expanding a node, if no obstacle is encountered in the expansion direction, the algorithm will continue to expand in that direction. If an obstacle is encountered, the algorithm will use a swap function to expand another random tree, which largely avoids the algorithm getting stuck in local optima.”); and
in response to a distance between a first tree node grown on the first exploration tree and a second tree node grown on the second exploration tree being not greater than a preset step length, connecting the first exploration tree and the second exploration tree to obtain a planned path of the moving object, wherein the second tree node is grown in the following manner ([0052]: “the algorithm will try to use the nearest node of the other tree as the expansion direction of this tree, so that the two trees intersect quickly.”; [0096]: “fixed step size E”):
selecting a tree node nearest to a target sampling point as a third tree node from a node set of the second exploration tree, and selecting a tree node on the first exploration tree nearest to the second exploration tree as a target tree node, wherein the target sampling point is obtained by extending sampling along the second tree node previously grown ([0052]: “the algorithm will try to use the nearest node of the other tree as the expansion direction of this tree, so that the two trees intersect quickly…. Figure 1 illustrates the extension process of the RRT-Connect algorithm. Referring to Figure 1, T1 and T2 are the two random search trees of RRT-Connect, N<sub>earest</sub>A and N<sub>earest</sub>B are the current points of the two random search trees, N<sub>new</sub>A and N<sub>new</sub>B are the new nodes (next nodes) of the two search trees, and N<sub>rand</sub>A and N<sub>rand</sub>B are the sampling points of the two search trees. The algorithm initially consists of two trees with the start and end points as root nodes, and extends them in a greedy manner, effectively reducing the expansion of the random tree into unknown regions.”); and
in response to a minimum distance between the third tree node and the obstacle being not less than a preset distance threshold, growing a tree node as the second tree node according to a direction from the third tree node to the target sampling point and a direction from the third tree node to the target tree node ([0056]: “Specifically, the length of the line connecting the starting point and the target point is L, and the distance between the candidate third node and the midpoint of the line connecting the starting point and the target point is L/2n, where n is a natural number not less than 2 (greater than or equal to 2); the third node is selected by gradually increasing n. When n takes any value, it is determined whether there is an obstacle in the area where the candidate third node is located. If there is no obstacle, it is selected as the third node; if there is an obstacle, the value of n is incremented to redetermine the candidate third node.”; [0057]: “It is understandable that when n takes any value, the third node has two alternatives. If neither of the two candidate nodes has any obstacles in its region, then one of the nodes is randomly selected as the third node. For example, when n=2, the distance between the candidate third node and the midpoint of the line connecting the starting point and the target point is L/4.”; and claim 6).
Re claim 12. A path planning apparatus, comprising:
a memory, a processor, and a computer program stored in the memory and executable by the processor, wherein the computer program, when executed by the processor, causes the processor to carry out a path planning method, the path planning method comprising ([0034]):
acquiring a motion space, a starting position, and an end position of a moving object, and information of an obstacle ([0010 and 0013]);
constructing a first exploration tree starting from the starting position and constructing a second exploration tree starting from the end position in the motion space, wherein the first exploration tree and the second exploration tree grow toward each other according to the information of the obstacle ([0052]); and
in response to a distance between a first tree node grown on the first exploration tree and a second tree node grown on the second exploration tree being not greater than a preset step length, connecting the first exploration tree and the second exploration tree to obtain a planned path of the moving object, wherein the second tree node is grown in the following manner ([0052 and 0096]):
selecting a tree node nearest to a target sampling point as a third tree node from a node set of the second exploration tree, and selecting a tree node on the first exploration tree nearest to the second exploration tree as a target tree node, wherein the target sampling point is obtained by extending sampling along the second tree node previously grown ([0052]); and
in response to a minimum distance between the third tree node and the obstacle being not less than a preset distance threshold, growing a tree node as the second tree node according to a direction from the third tree node to the target sampling point and a direction from the third tree node to the target tree node ([0056-0057] and claim 6).
Re claim 13. A non-transitory computer-readable storage medium, storing computer-executable instructions which, when executed by a processor, cause the processor to carry out a path planning method, the path planning method comprising ([0034]):
acquiring a motion space, a starting position, and an end position of a moving object, and information of an obstacle ([0010 and 0013]);
constructing a first exploration tree starting from the starting position and constructing a second exploration tree starting from the end position in the motion space, wherein the first exploration tree and the second exploration tree grow toward each other according to the information of the obstacle ([0052]); and
in response to a distance between a first tree node grown on the first exploration tree and a second tree node grown on the second exploration tree being not greater than a preset step length, connecting the first exploration tree and the second exploration tree to obtain a planned path of the moving object, wherein the second tree node is grown in the following manner ([0052 and 0096]):
selecting a tree node nearest to a target sampling point as a third tree node from a node set of the second exploration tree, and selecting a tree node on the first exploration tree nearest to the second exploration tree as a target tree node, wherein the target sampling point is obtained by extending sampling along the second tree node previously grown ([0052]); and
in response to a minimum distance between the third tree node and the obstacle being not less than a preset distance threshold, growing a tree node as the second tree node according to a direction from the third tree node to the target sampling point and a direction from the third tree node to the target tree node ([0056-0057] and claim 6).
The independent claims have been addressed with prior art as best understood by the examiner in light of the 35 USC §112(b) clarity issues identified above. The dependent claims will be considered for potential 35 USC §102 and 103 issues upon clarification of the claim language.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to SPENCER D PATTON whose telephone number is (571)270-5771. The examiner can normally be reached Monday to Friday 9:00-5:00 ET.
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.
/SPENCER D PATTON/ Primary Examiner, Art Unit 3656