# US 10,480,947 B2 · Boolean satisfiability (SAT) reduction for geometry and kinematics agnostic multi-agent planning > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,480,947 B2 - Document ID: US10480947B2 - Status: Granted - Kind: B2 - Application number: 15/387,503 - Filed: 2016-12-21 - Published: 2018-06-21 - Granted: 2019-11-19 - Earliest claimed: 2016-12-21 - Assignees: X Development LLC - Applicants: X Development LLC - Inventors: Geoffrey Lalonde; Peter Anderson-Sprecher - Web page: https://patentgrep.com/patent/US10480947B2 ## CPC - G01C 21/206: {specially adapted for indoor navigation} - G01C 21/3407: {specially adapted for specific applications} - G01C 21/3453: {Special cost functions, i.e. other than distance or default speed limit of road segments} - Y10S 901/01: Mobile robot - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) - Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS ## Abstract Systems and methods related to roadmaps for robotic devices are provided. A computing device can receive a roadmap representing a plurality of paths through an environment. The computing device can discretize the roadmap to obtain a discrete planning graph having a plurality of states corresponding to discretized segments of the plurality of paths of the roadmap such that states corresponding to adjacent discretized path segments are connected in the discrete planning graph. The computing device can determine a Boolean equation representing at least a portion of the discrete planning graph. The computing device can determine a sequence of states from the plurality of states of the discrete planning graph such that the determined sequence of states satisfies the Boolean equation. The computing device can provide a route through the environment for a robotic device based on the determined sequence of states. ## Claims ### Claim 1 A method, comprising: receiving, by a computing device, a roadmap representing a plurality of paths through an environment; discretizing the roadmap, by the computing device, to obtain a discrete planning graph, wherein the discrete planning graph comprises a plurality of states corresponding to discretized path segments of the plurality of paths of the roadmap such that states corresponding to adjacent discretized path segments are connected in the discrete planning graph; determining, by the computing device, a Boolean equation representing at least a portion of the discrete planning graph, wherein the Boolean equation comprises a plurality of Boolean clauses, wherein the plurality of Boolean clauses comprise a plurality of Boolean variables, wherein each Boolean variable of the plurality of Boolean variables represents a possible state of a robotic device in the discrete planning graph at one of a plurality of times; determining, by the computing device, a set of values comprising a value of true or false for each Boolean variable of the plurality of Boolean variables, wherein the set of values satisfies the Boolean equation, wherein the set of values indicates a sequence of states for the robotic device to occupy from the plurality of states of the discrete planning graph, and wherein the sequence of states for the robotic device to occupy is represented by Boolean variables having a determined value of true; and providing, by the computing device, a route through the environment for the robotic device to cause the robotic device to occupy each state in the sequence of states over the plurality of times. ### Claim 2 (depends on 1) The method of claim 1, wherein discretizing the roadmap to obtain the discrete planning graph comprises: determining an uniform path length based on one or more parameters; segmenting the roadmap so that each discretized path segment has a path length that is substantially equal to the uniform path length; determining the plurality of states based on the segmented roadmap; and determining a plurality of edges that connect the plurality of states based on connectivity of the roadmap. ### Claim 3 (depends on 2) The method of claim 2, wherein the one or more parameters include one or more of: a time parameter and a length parameter. ### Claim 4 (depends on 1) The method of claim 1, wherein determining the Boolean equation representing at least a portion of the discrete planning graph comprises determining the Boolean equation representing at least a portion of the discrete planning graph based on a footprint of the robotic device. ### Claim 5 (depends on 4) The method of claim 4, wherein determining the Boolean equation representing at least a portion of the discrete planning graph based on the footprint of the robotic device comprises: determining the footprint of the robotic device; for each discretized path segment of the discretized path segments, determining a swept path segment by at least sweeping the footprint of the robotic device over the discretized path segment; determining whether at least one pair of swept path segments overlap; and after determining that at least one pair of swept path segments do overlap, adding at least one collision clause to the Boolean equation representing a condition that the at least one pair of swept path segments do overlap. ### Claim 6 (depends on 5) The method of claim 5, wherein the robotic device is part of a plurality of robotic devices, and wherein the at least one collision clause is used to simultaneously plan non-conflicting routes for the plurality of robotic devices. ### Claim 7 (depends on 1) The method of claim 1, wherein the roadmap comprises a plurality of intersections, and wherein discretizing the roadmap to obtain a discrete planning graph comprises removing one or more intersections of the roadmap prior to discretizing the roadmap. ### Claim 8 (depends on 1) The method of claim 1, wherein the Boolean equation is expressed in a conjunctive normal form. ### Claim 9 (depends on 1) The method of claim 1, wherein determining the set of values for the plurality of Boolean variables which satisfies the Boolean equation comprises using a SAT solver. ### Claim 10 (depends on 1) The method of claim 1, wherein the plurality of Boolean clauses comprise at least a start and goal clause, a flow conservation clause, and a collision clause. ### Claim 11 A computing device, comprising: one or more processors; and data storage including at least computer-executable instructions stored thereon that, when executed by the one or more processors, cause the computing device to perform functions comprising: receiving a roadmap representing a plurality of paths through an environment; discretizing the roadmap to obtain a discrete planning graph, wherein the discrete planning graph comprises a plurality of states corresponding to discretized path segments of the plurality of paths of the roadmap such that states corresponding to adjacent discretized path segments are connected in the discrete planning graph; determining a Boolean equation representing at least a portion of the discrete planning graph, wherein the Boolean equation comprises a plurality of Boolean clauses, wherein the plurality of Boolean clauses comprise a plurality of Boolean variables, wherein each Boolean variable of the plurality of Boolean variables represents a possible state of a robotic device in the discrete planning graph at one of a plurality of times; determining a set of values comprising a value of true or false for each Boolean variable of the plurality of Boolean variables, wherein the set of values satisfies the Boolean equation, wherein the set of values indicates a sequence of states for the robotic device to occupy from the plurality of states of the discrete planning graph, and wherein the sequence of states for the robotic device to occupy is represented by Boolean variables having a determined value of true; and providing a route through the environment for the robotic device based on the determined sequence of states to cause the robotic device to occupy each state in the sequence of states over the plurality of times. ### Claim 12 (depends on 11) The computing device of claim 11, wherein discretizing the roadmap to obtain the discrete planning graph comprises: determining an uniform path length based on one or more parameters; segmenting the roadmap so that each discretized path segment has a path length that is substantially equal to the uniform path length; determining the plurality of states based on the segmented roadmap; and determining a plurality of edges that connect the plurality of states based on connectivity of the roadmap. ### Claim 13 (depends on 12) The computing device of claim 12, wherein the one or more parameters include one or more of: a time parameter and a length parameter. ### Claim 14 (depends on 11) The computing device of claim 11, wherein determining the Boolean equation representing at least a portion of the discrete planning graph comprises determining the Boolean equation representing at least a portion of the discrete planning graph based on a footprint of the robotic device. ### Claim 15 (depends on 14) The computing device of claim 14, wherein determining the Boolean equation representing at least a portion of the discrete planning graph based on the footprint of the robotic device comprises: determining the footprint of the robotic device; for each discretized path segment of the discretized path segments, determining a swept path segment by at least sweeping the footprint of the robotic device over the discretized path segment; determining whether at least one pair of swept path segments overlap; and after determining that at least one pair of swept path segments do overlap, adding at least one collision clause to the Boolean equation representing a condition that the at least one pair of swept path segments do overlap. ### Claim 16 (depends on 15) The computing device of claim 15, wherein the robotic device is part of a plurality of robotic devices, and wherein the at least one collision clause is used to simultaneously plan non-conflicting routes for the plurality of robotic devices. ### Claim 17 (depends on 11) The computing device of claim 11, wherein the roadmap comprises a plurality of intersections, and wherein discretizing the roadmap to obtain a discrete planning graph comprises removing one or more intersections of the roadmap prior to discretizing the roadmap. ### Claim 18 (depends on 11) The computing device of claim 11, wherein the Boolean equation is expressed in a conjunctive normal form. ### Claim 19 A non-transitory computer readable medium having stored thereon instructions, that when executed by one or more processors of a computing device, cause the computing device to perform functions comprising: receiving a roadmap representing a plurality of paths through an environment; discretizing the roadmap to obtain a discrete planning graph, wherein the discrete planning graph comprises a plurality of states corresponding to discretized path segments of the plurality of paths of the roadmap such that states corresponding to adjacent discretized path segments are connected in the discrete planning graph; determining a Boolean equation representing at least a portion of the discrete planning graph, wherein the Boolean equation comprises a plurality of Boolean clauses, wherein the plurality of Boolean clauses comprise a plurality of Boolean variables, wherein each Boolean variable of the plurality of Boolean variables represents a possible state of a robotic device in the discrete planning graph at one of a plurality of times; determining a set of values comprising a value of true or false for each Boolean variable of the plurality of Boolean variables, wherein the set of values satisfies the Boolean equation, wherein the set of values indicates a sequence of states for the robotic device to occupy from the plurality of states of the discrete planning graph, and wherein the sequence of states for the robotic device to occupy is represented by Boolean variables having a determined value of true; and providing a route through the environment for the robotic device to cause the robotic device to occupy each state in the sequence of states over the plurality of times.