Map Search

1 collaborator

Introduction

The shortest path problem is widespread in software optimisation with online application but also prevalent real-world design from road networks, logistics, communications and even community detection.

Common variations to tackle the shortest path problem involve different architecture of algorithms. The first of which is the use of single source shortest path, this finds the sum of weights of the edges in the paths, with the objective to minimize this sum. Another variation is the breadth first search. BFS finds the shortest path from the source to the goal in an unweighted graph.

In choosing algorithms to solve the shortest path problem many present themselves as worthy choice. Dijkstra’s algorithm is one form of the greedy algorithm. This includes a graph search algorithm used to solve the problem with a single source on a graph with no negative side cost. This is a common algorithm used in routing, with the main side affect of the high accuracy it achieves is the slow computation time.

In comparison to this algorithm A* search is used. A* search is very similar in application to Dijkstra’s although uses a heuristic for optimisation. This heuristic which trades accuracy, optimality, completeness, or precision for speed. This heuristic estimate changes drastically how the algorithm performs, therefore choosing the correct function in this respect is important.

Through changing the number of generated nodes and connection density on the model, differences between the two algorithms emerge. Adding the complexity of changing heuristics in the A* search algorithm will also introduce some interesting findings.

Agents

Turtles are the default agent used for the nodes on the network. They are stationary and have one unique property of dist, which represents the distance travelled to reach that node from the start node. This is used only in the Dijkstra’s algorithm implementation. dist is initialised for each node at infinity, apart from the start node given a dist value of 0 given there is no distance required to travel to reach it.

Turtles are connected to one another using links. These are the default implementation of links with added property of value. This can be thought of as the weight of the connection between nodes.

Searchers are agents used in the application of A* search, actively moving between nodes to find the shortest path.

The first property of the searcher is the memory. This stores the path from the start node to the current node being explored. This list is treated as a queue with the most recently added node being added to the start of the list. The first searcher to reach the node holds the memory of the nodes taken for the shortest distance to the goal.

The next property which corresponds to the memory component of the searcher is the cost. The cost measures the real distance travelled between the start node and the current node. Similar to the cost is the total expected cost of the searcher. This is calculated at first by the sum of the current cost of the searcher and the heuristic output to the finish node, referred to as the goal node in the application. This value is updated in the same way after calculating the new heuristic at a new node.

In order to track the current location of the searcher, the property localization is employed, this stores the value of the turtle node currently being explored.

The last property of the searcher is the Boolean variable active. Using the Boolean property allows for the searcher to turned on and off dynamically. In the algorithm only searchers who are active are used to find the next following nodes. During the movement of the searcher the property is set to false, in order to prevent the searcher from being manipulated.

Parameters

During the setup process the nodes and edges are generated. This includes the allocation of the start and finish node. The process of generating the start and finish node is random in order to prevent any human bias being introduced. Last in the setup is setting the colour of all links to white for improved visual understanding in the interface.

In setting up the nodes turtle shape is default to circle and each x and y coordinate is randomly allocation inside the window size given. For the edges the number of links is initialised at 0 at the beginning, then incremented by 2 each time a new connection between nodes is made on account of there being edges in both direction between each node. The value of each edge is calculated by the distance between each node. This is the Euclidean distance under the distance function in the NetLogo language.

Users have the choice to show or hide the value of each edge for insight of the algorithm or clearer visuals.

Global variables are in use to monitor start and finish node agents. The number of edges is tracked to iterate over in the edge setup function. An agent list of nodes that haven’t been visited for use in the Dijkstra’s search. A variable for plotting the value of the distance travelled to reach the final rode is also made. gorithm or clearer visuals as can be an issue with too may edges on the network.

Method

Dijkstra’s Algorithm steps: 1. Set all nodes dist to infinity except for the starting node set distance to For this application the use of 99999 is sufficient for infinity as this far exceeds the great possible distance that can be generated in the environment of this size. 2. Set all nodes, including starting nodes to the list of nodes not visited. 3. Set the non-visited node with the smallest current distance as the current node "C." 4. For each neighbour “N” of your current node: add the current distance of “C” with the weight of the edge connecting “C” –> “N." If it's smaller than the current distance of “N," set it as the new current distance of “N." 5. Remove the current node “C” from the list of nodes not visited. 6. Repeat the step above from step 3 until the destination point is visited.

A* Algorithm steps: 1. Create a searcher node at the start node. a. Set localization to the start node. b. Set cost 0. c. Set total expected cost = cost + heuristic(goal) d. Initialize the memory to include current position. e. Change active to true. 2. Select active searcher with lowest total expected cost "S". 3. Set S active false. 4. Ask nodes connected to node at S: a. Measure the cost + value of edge between nodes "c". b. If no other searcher at that node have a lower cost: i. Create a searcher. ii. Set cost to c. iii. Set active to true. iv. Set localization to current node. v. Add the memory of this searcher to the end of the memory. c. Ask other searchers at that node to die. 5. Repeat steps 2 to 4 until an active searcher reaches the goal. 6. Output the memory of that searcher as the shortest path.

VALIDATION

The model demonstrates that the Short Path Problem can be solved via the two algorithm proposed. The heuristic function implemented in the A* Algorithm does not provide the level of accuracy in finding the shortest path as the Dijkstra’s algorithm does in comparison. However, the use of the heuristic provides a significant benefit in the computational complexity and time required to search for the goal node. Over the span of 500 iterations of running the two algorithms on the same network samples, it can be seen that the majority of runs display the A* Algorithm returning an increase of 1 to 3 steps higher than the control algorithm Dijkstra’s.

THINGS TO TRY

Changing the value of each slider to see the limit of your implemented heuristic.

EXTENDING THE MODEL

Implementation of new heuristic functions on the A* search algorithm.

NETLOGO FEATURES

This model uses the link primitives. It also makes heavy use of lists.

RELATED MODELS

Virus on a network from the NetLogo Models Library implements a similar network structure.

CREDITS AND REFERENCES

Using random weighted network https://ccl.northwestern.edu/netlogo/docs/nw.html

A* algorithm implementation http://www.cs.us.es/~fsancho/?e=131

Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

Click to Run Model

breed [searchers searcher]

globals [
  start-node
  finish-node
  number-edges
  notVisited
  a-total
]

turtles-own [
  dist
]

searchers-own [
  memory
  cost
  total-expected-cost
  localization
  active?
]

links-own [
  value
]

;--------------- SETUP ---------------

to setup
  clear-all
  setup-nodes
  setup-edges
  random-select
  ask links [ set color white ]
end 

to setup-nodes
  set-default-shape turtles "circle"
  create-turtles number-of-nodes [
    setxy (random-xcor * 0.95) (random-ycor * 0.95)
    set color blue
    set size .75
  ]
end 

to setup-edges
  set number-edges 0

  let num-links (average-node-degree * number-of-nodes) / 2
  while [count links < num-links ] [
    ask one-of turtles [
      let choice (min-one-of (other turtles with [not link-neighbor? myself])
                   [distance myself])
      if choice != nobody [
        let node-weight [distance myself] of choice
        create-link-with choice [set value round node-weight]
        set number-edges (number-edges + 1)
      ]
    ]
  ]

  repeat number-of-nodes [
    layout-spring turtles links 0.3 (world-width / (sqrt number-of-nodes) ) 10
  ]

  ask links [
    ifelse show-weights? [
      set label precision value 4
    ] [
      set label ""
    ]
  ]
end 

to random-select
  ask one-of turtles [
    set color green
    set start-node self
    set size 1.25
  ]
  ask one-of turtles [
    set color red
    set finish-node self
    set size 1.25
  ]
end 

;----------------- GO -----------------

to go-dijkstra
  dijkstra-search
end 

to dijkstra-search
  set notVisited turtles
  ask turtles [set dist 99999]
  ask start-node [ set dist 0 ]

  while [count notVisited > 0] [
    let current min-one-of notVisited [dist]
    set notVisited notVisited with [self != current]
    ask current [
      ask link-neighbors [
        let link-value ([value] of link-with current)
        let newDist ([dist] of current + link-value)
        if newDist < dist
        [set dist newDist]
      ]
    ]
  ]
end 

to go-astar
  set a-total 0
  let path (A* start-node finish-node)
  if path != false [highlight-path path]
end 

to-report A* [#Start #Goal]
  ask #Start [
    hatch-searchers 1 [
      set shape "circle"
      set color red
      set localization myself
      set memory (list localization)
      set cost 0
      set total-expected-cost cost + heuristic #Goal
      set active? true
    ]
  ]

  while [not any? searchers with [localization = #Goal] and any? searchers with [active?]] [
    ask min-one-of (searchers with [active?]) [total-expected-cost] [
      set active? false
      let this-searcher self
      let Lorig localization
      ask ([link-neighbors] of Lorig) [
        let connection link-with Lorig
        let c ([cost] of this-searcher) + [link-length] of connection
        if not any? searchers-in-loc with [cost < c] [
          hatch-searchers 1 [
            set shape "circle"
            set color red
            set localization myself
            set memory lput localization ([memory] of this-searcher)
            set cost c
            set total-expected-cost cost + heuristic #Goal
            set active? true
            ask other searchers-in-loc [die]
          ]
        ]
      ]
    ]
  ]

  let res false

  if any? searchers with [localization = #Goal] [
    let lucky-searcher one-of searchers with [localization = #Goal]
    set res [memory] of lucky-searcher
  ]
  ask searchers [die]
  report res
end 

to-report heuristic [#Goal]
  report [distance [localization] of myself] of #Goal
end 

to-report searchers-in-loc
  report searchers with [localization = myself]
end 

to-report highlight [x y]
  ask x [
    ask link-with y [set color yellow set thickness .4]
    set a-total a-total + [value] of link-with y
  ]
  report y
end 

to highlight-path [path]
  let a reduce highlight path
end

There are 2 versions of this model.

		Uploaded by	When	Description	Download
		Sebastian Dixon	over 2 years ago	Info	Download this version
		Sebastian Dixon	over 2 years ago	Initial upload	Download this version

Attached files

File	Type	Description	Last updated
Map Search.png	preview	Preview for 'Map Search'	over 2 years ago, by Sebastian Dixon	Download

This model does not have any ancestors.

This model does not have any descendants.

NetLogo