System and method for multi-goal path planning
AssigneeTeradyne, Inc.
InventorChalongrath Pholsiri
Life of this patent
Estimating the term…
Abstract
A method and computing system comprising identifying a plurality of robot configurations for each inspection point of a plurality of inspection points of a problem. A graph may be generated with each feasible robot configuration as a node on the graph. A distance may be calculated between a pair of feasible robot configurations. A shortest complete path connecting each node on the graph may be obtained based upon, at least in part, the distance between the pair of feasible robot configurations.
Claims34
A method for multi-goal path planning comprising:
- defining a plurality of inspection points of a problem;
- identifying a plurality of robot configurations for each inspection point of the plurality of inspection points of the problem;
- generating a graph with each feasible robot configuration as a node on the graph;
- calculating a distance between a pair of feasible robot configurations, wherein the distance between the pair of feasible robot configurations is a measurement of time;
- obtaining a shortest complete path connecting each node on the graph based upon, at least in part, the distance between the pair of feasible robot configurations, wherein obtaining the shortest complete path comprises applying, using at least one processor, a traveling salesman problem (“TSP”) methodology based upon, at least in part, the graph;
- obtaining a visit order from the TSP methodology;
- applying, using at least one processor, a path planning methodology to obtain a path between a plurality of neighboring nodes that are not directly connected;
- and
- controlling a robot, based upon, at least in part, the shortest complete path.
A computing system including a processor and memory configured to perform operations comprising:
- defining a plurality of inspection points of a problem;
- identifying a plurality of robot configurations for each inspection point of the plurality of inspection points of the problem;
- generating a graph with each feasible robot configuration as a node on the graph;
- calculating a distance between a pair of feasible robot configurations, wherein the distance between the pair of feasible robot configurations is a measurement of time;
- obtaining a shortest complete path connecting each node on the graph based upon, at least in part, the distance between the pair of feasible robot configurations, wherein obtaining the shortest complete path comprises applying, using at least one processor, a traveling salesman problem (“TSP”) methodology based upon, at least in part, the graph;
- obtaining a visit order from the TSP methodology;
- applying, using at least one processor, a path planning methodology to obtain a path between a plurality of neighboring nodes that are not directly connected;
- and
- controlling a robot, based upon, at least in part, the shortest complete path.
Dependencies are inferred from the claim text.