Search code examples
c#.netpath-findingtraveling-salesman

Traveling salesman prob on 2d map with walls (obstacles) so pathfinding needed

I need to find optimal path between a number of points on a 2d map. The 2d map is of a building and will simply have where you can not go (through walls) and all the points on the map. So it's not really a map, rather lines you cannot go through with points to pass through.

  • I have a number of points, say between 20 and 500
  • I start with one that I select and then need the route calculated for most optimal path.

I would love hints for where to look for this travelling salesman problem with obstacles. Or even better, done library for doing it.

Bonuses

  • Things like doors can be weighted as they are less fun to pass through back and forth.
  • Possibility of prioritizing/Weighting the ability to end close to where you started.
  • Selecting areas as passable but annoying (weighting down)
  • .Net/C# code that I can use, I want to use this both on .NET MVC project and Xamarin mobile project so .net code would be great (if code exists)

Update example

enter image description here In my example here we have an office. Now I have not thought every detail out so this is merely an example.

  • All the purple dots need to be checked
  • Yellow area could mean annoying to pass through but doable
  • Red could mean not active but can be passed if no other option exists.
  • Blue (walls) are impenetrable and can not be passed.
  • Green is doors, weighted down possibly as it's annoying to go trough closed doors (usually this would probably make sense anyway as the dots in a room would be easiest to check together.
  • The user would go to one dot, check it, then the software should tell him which one to do next until he is done.
  • Bonus could be given for ending close to start place. So for instance in this example, if the red area was normal and contained dots it would have been easy to make it a loop. (So the user comes back close to where he started)
  • Finally I suppose it would also be smart to differentiate outdoors areas as you would need to get dressed for outdoors, so you only want to go out once.
  • Also it could be smart to be able to prioritize ending on a point close to stairwell to next floor if they intend to check multiple floors at once.
  • Of course would have more more complex and larger plans the this exmaple.

Again sorry for just brainstorming out ideas but I have never done this kind of work and is happy for any pointers :-)

Solution

  • Let N be the set of nodes to visit (purple points). For each i and j in N, let c(i,j) be the distance (or travel time) to get from i to j. These can be pre-computed based on actual distances plus walls, doors, other barriers, etc.

    Now, you could then add a penalty to c(i,j) if the path from i to j goes through a door, "annoying" area, etc. But a more flexible way might be as follows:

    Let k = 1,...,K be the various types of undesirable route attributes (doors, annoying areas, etc.). Let a_k(i,j) be the amount of each of these attributes on the path from i to j. (For example, suppose k=1 represents door, k=2 represents yellow areas, k=3 represents outside. Then from an i in the break area to j in the bathroom might have a_1(i,j) = 1, and from an i to a j both in the yellow areas would have a_2(i,j) = 0.5 or 2.0 or however annoying that area is, etc.)

    Then, let p_k be a penalty for each unit of undesirable attribute k -- maybe p_1 = 0.1 if you don't mind going through doors too much but p_2 = 3.0 if you really don't like yellow areas.

    Then, let c'(i,j) = c(i,j) + sum{k=1,...,K} p_k * a_k(i,j). In other words, replace the actual distance with the distance plus penalties for all the annoyances. The user can set the p_k values before the optimization in order to express his/her preferences among these. The final penalties p_k * a_k(i,j) should be commensurate with the distance units used for c(i,j), though -- you don't want distances of 100m but penalties of 1,000,000.

    Now solve a TSP with distances given by c'(i,j).

    The TSP requires you to start and end at the same node, so that preference is really a constraint. If you're going to solve for multiple floors simultaneously, then the stairway times would be in the c(i,j) so there's no need to explicitly encourage routes that end near a stairway -- the solution would tend to do that anyway since stairs are slow. If you're going to solve each floor independently, then just set the start node for each floor equal to the stairway. I wouldn't do anything about the red (allowable but unused) areas -- that would already be baked into the c(i,j) calculations.

    Hope this helps.