KR20120062462A | 2012-06-14 | |||
US9475195B2 | 2016-10-25 | |||
US20140089049A1 | 2014-03-27 |
Claims Following is the claim for this invention: - 1. In this invention we have different tasks or jobs that robots can carry out and these tasks involve moving from point A to point B in an area which could be a rectangular two-dimensional grid. We classify these robots carrying out the above kind of tasks into different groups such that all robots from different groups are not deadlocked (cannot move) or do not require huge number of steps to be backtracked (using backtracking algorithm) for other robots and the blocking time for a robot at a cell in the rectangular grid area is very small. We also not allow robots in certain groups to enter into certain cells to avoid deadlocks or to minimize wait times for lower priority robots. We do give priorities to different robotic groups so that in case paths intersect in the rectangular grid the lower priority robot will wait for the higher priority robot to step towards its destination and make way for it. Also note here we consider the two- dimensional rectangular grid to be of m rows and n columns with each cell of size 1 square unit and total area of the rectangular grid is of size m*n square unit. We do maintain for each robot in different groups a hash table consisting of the current or origin cell position (i, j) as the key and the value is the linked list of various paths (or path objects containing sequence of cells to be visited to reach the destination point from current point which can be derived using dynamic programming technique or backtracking technique) available to take to reach the destination point (x, y) sorted by minimum cost required to reach the destination point. For each robot we start off by taking the minimum cost path and if we are blocked because of higher priority robots in the way or if some other robots in the way do not move or for other reasons we consider other paths from the hash table. The above novel technique of classifying different robots depending upon the path they take to accomplish their task is the claim for this invention. |
In this invention we have different tasks or jobs that robots can carry out and these tasks involve moving from point A to point B in an area which could be a rectangular two-dimensional grid. We classify these robots carrying out the above kind of tasks into different groups such that all robots from different groups are not deadlocked (cannot move) or do not require huge number of steps to be backtracked (using backtracking algorithm) for other robots and the blocking time for a robot at a cell in the rectangular grid area is very small. We also not allow robots in certain groups to enter into certain cells to avoid deadlocks or to minimize wait times for lower priority robots. We do give priorities to different robotic groups so that in case paths intersect in the rectangular grid the lower priority robot will wait for the higher priority robot to step towards its destination and make way for it. Also note here we consider the two-dimensional rectangular grid to be of m rows and n columns with each cell of size 1 square unit and total area of the rectangular grid is of size m*n square unit. We do maintain for each robot in different groups a hash table consisting of the current or origin cell position (i, j) as the key and the value is the linked list of various paths (or path objects containing sequence of cells to be visited to reach the destination point from current point which can be derived using dynamic programming technique or backtracking technique) available to take to reach the destination point (x, y) sorted by minimum cost required to reach the destination point. For each robot we start off by taking the minimum cost path and if we are blocked because of higher priority robots in the way or if some other robots in the way do not move or for other reasons we consider other paths from the hash table.
Next Patent: IMPROVED SENSOR DEVICE AND USE OF THIS DEVICE FOR DETECTING OSCILLATIONS