python - Checking for Obstacle in Path / Shortest Path -


i working on simulated robotics program (using morse-robot simulator), involves controlling robot move around room (using spoken language) various boxes, other objects, , other robots. i'd robot to: 1. avoid obstacles (boxes, other robots) 2. find shortest path

for now, i'm ignoring problem of dynamic obstacles, such other robots changing position, though that'll come play eventually.

i aware of a* search , dijkstra's algorithm, , have implemented similar graph-search algorithms in past; however, these procedures involve graph/grid search. currently, robot's world model represented dictionary of objects within world, opposed tile-based grid indicates whether tiles filled or not. e.g.:

{box={position: (3, 4)...}, robot={position: (0,0)...}}

if necessary, go through process of changing world model grid/graph representation, seems me shouldn't necessary. shortest-path, morse simulator move "crow's distance" point point b - ploughing right through obstacles in way.

thus, i'd add control feature checks if obstacles in current path between robot , destination, , if so, suggests alternative, n-part route.

what i've implemented far, in python, checks whether object falls within range of slope between point , point b:

def check_for_obstacles(origin, destination):      slope = get_slope(origin, destination)      obstacles = []      initialx = origin[0]      obj in world:           worldobj = getattr(world, obj)           pos = [worldobj.pos.x, worldobj.pos.y]           yint = slope * pos[0] + origin[1]           diff = abs(pos[1] - yint)           if diff < 2: # hard-coded footprint of object,               obstacles.append(obj)      return obstacles 

in few test-cases, seems work. presumably, once list of obstacles in path, i'll find triangulation new path, , continually check obstacles go. seem reasonable solution, or overlooking obvious?


Comments

Popular posts from this blog

c++ - Difference between pre and post decrement in recursive function argument -

php - Nothing but 'run(); ' when browsing to my local project, how do I fix this? -

php - How can I echo out this array? -