Shortest path & Obstacle avoidance using AddCircuit

I observed a cat gracefully navigating through a cluttered room, skillfully sidestepping the obstacles scattered on the floor. I asked him the tricks and discovered that Mr. Tom is using ORTools AddCircuit function to do the job. Here is the story:

AddCircuit

The AddCircuit function is described as follows:

def AddCircuit(self, arcs) Adds a circuit constraint from a sparse list of arcs that encode the graph. A circuit is a unique Hamiltonian path in a subgraph of the total graph. In case a node 'i' is not in the path, then there must be a loop arc 'i -> i' associated with a true literal. Otherwise this constraint will fail. a list of arcs. An arc is a tuple (source_node, destination_node, literal). The arc is selected in the circuit if the literal is true. Both source_node and destination_node must be integers between 0 and the number of nodes - 1.

Upon hearing the name, my initial response involved thoughts of an electric circuit, and I was pleasantly surprised by its connection to optimization. It took me a while to correctly understand the true meaning of it (at least I think I know).

Consider a connected graph as follows:

The question is how to find a Hamiltonian path with min length?

First, we need to generate the graph's data:

Then, the ORTools model should be created:

The idea is providing a list of possible arcs :

[(i,j,Boolean Variable) , .... ]  i is not the same as j        

The AddCircuit function will create a closed path considering all nodes of the graphs. Here is the result (reminds me the TSP):

It is also possible to exclude some nodes, let's exclude the node 8. We need to add this arc (8,8,True) to the list of arcs.

model = cp_model.CpModel()
solver = cp_model.CpSolver()
nodes = [n for n in G.nodes()]
U = {(i,j):model.NewBoolVar(f"connection_{i}_{j}")  for (i,j) in connect}
arcs = [(i,j,v) for (i,j),v in U.items() ]
arcs += [(8,8,True)]
model.AddCircuit(arcs)
expressions = [v*connect[i,j] for (i,j),v in U.items() ]
model.Minimize(sum(expressions))
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
  print("Optimal solutionis found")        

Result:

With all this said, let's skip to the fun part:

How can we use AddCircuit for finding the shortest path ?

Consider this example: the intention is to find the shortest path between the start (blue) and final (orange) point. Assume that we can move one step horizontally, vertically or diagonally at a time.

The AddCircuit will create a closed loop. (I limited the time to 10 seconds , thta's why it is not Optimal).

What we can do is to

• Allow not selection of some nodes

arcs += [(n,n,Boolean Variable) for n in nodes]        

• Create a return path and let the AddCircuit find the outbound path.

arcs += [(fn,st,True)]        

The green path is determined by the ORTools.

Let's make the problem more complicated:

How to find the shortest collision-free path among some obstacles?

The process is straightforward. Simply eliminate any arcs containing nodes within the obstacles and then proceed to resolve the problem.

How to find the minimum exposure path among some pulutant obstacles?

The following visualization shows the level of exposure of each point to the pollution. The exposure index diminishes as we move farther away from the obstacles.

• The objective function should be updated:

OF = sum_{ij} (Ii+Ij)*Uij        

The codes are available in Github repo

Applications:

1. Network Routing: the most efficient routes for data transmission, optimizing network traffic.
2. Logistics and Supply Chain: Optimizing transportation routes for delivery vehicles to minimize time, fuel, and costs in logistics and supply chain management.
3. Map Applications: Navigation systems and map applications use shortest path algorithms to calculate the quickest routes for driving, walking, or cycling.
4. Robotics: Pathfinding algorithms are crucial in robotics for guiding robots through environments by finding the shortest path while avoiding obstacles.
5. Traffic Engineering: Traffic flow optimization in urban planning to alleviate congestion by finding the most efficient paths for vehicles.
6. Telecommunications: Planning optimal routes for the installation of cables and communication lines to reduce infrastructure costs.
7. Circuit Design: the shortest paths in integrated circuits to optimize signal propagation and reduce delay.
8. Emergency Evacuation Planning: Finding the quickest evacuation routes during emergencies, such as natural disasters or accidents.
9. Urban Planning: Planning efficient routes for public transportation, waste collection, and emergency services to enhance the functionality of cities.
10. Social Network Analysis: Analyzing relationships and connections in social networks to find the shortest paths between individuals or groups.
11. Pipeline Planning: In oil and gas industries, optimizing the routes of pipelines to minimize costs and environmental impact.