A* implementation using prolog and python

Project installation instructions, including SWI-Prolog

Installing SWI-Prolog

Linux

1. Using Package Manager:

   • Debian/Ubuntu:

     sudo apt update
     sudo apt install swi-prolog

   • Fedora:

     sudo dnf install swipl

   • Arch Linux:

     sudo pacman -S swi-prolog

2. From Source:

   • Download the latest version from the SWI-Prolog website.
   • Extract the tarball and navigate into the directory:

     tar -xzf swipl-X.Y.Z.tar.gz
     cd swipl-X.Y.Z

   • Run the following commands:

     ./configure
     make
     sudo make install

macOS

1. Using Homebrew: If you don’t have Homebrew installed, you can install it using:

   /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"

   Then install SWI-Prolog:

   brew update
   brew install swi-prolog

2. From Source:

   • Download the latest version from the SWI-Prolog website.
   • Extract, configure, and install using:

     tar -xzf swipl-X.Y.Z.tar.gz
     cd swipl-X.Y.Z
     ./configure
     make
     sudo make install

Windows

1. Using Installer:

   • Go to the SWI-Prolog downloads page.
   • Download the Windows installer (usually an .exe file).
   • Run the installer and follow the on-screen instructions.

2. Using Chocolatey: If you have Chocolatey installed, you can use:

   choco install swi-prolog

Verification

After installation, you can verify that SWI-Prolog is installed correctly by opening a terminal or command prompt and typing:

swipl

This should launch the SWI-Prolog interpreter. If you see the prompt, you're good to go!

Installing Dependencies

To install the required packages for this project, navigate to your project directory and run:

pip install -r requirements.txt

Running the Example

To run the A* example using Streamlit, execute the following command in your terminal:

streamlit run example_streamlit.py

Once the application is running, open your web browser and go to http://localhost:8501 to view the Streamlit interface. Make sure you have Streamlit installed in your environment before running the command.

Astar program

This document details the implementation of the Prolog A* algorithm, designed for pathfinding between streets. The algorithm utilizes a graph-based structure generated by the accompanying script get_map.py. This script constructs a graph, including the respective nodes and edges, representing the street layout for the pathfinding process.
The Prolog predicate astar/4 serves as the main entry point for executing the A* pathfinding algorithm. It is designed to find the shortest path from a given starting node (Start) to a destination node (Goal), returning the computed path (Path) and the total cost (Cost) of traversal.

Predicate Definition:

astar(Start, Goal, Path, Cost)

Parameters:

•	Start: The starting node from which the search begins.
•	Goal: The target node where the search should end.
•	Path: The list of nodes representing the shortest path from Start to Goal.
•	Cost: The total cost associated with traversing the computed path.

Get Map

This project utilizes the osmnx library to extract a city’s street network data. The library generates a structured graph, mapping node IDs to sequential integers and defining the corresponding edges. This processed information is then written to a file named city_data.pl. The output in this file is structured in the following format:

Locations Section:

% Locations in the city (Nodes)
location(1, 'Intersection 1').
location(2, 'Intersection 2').
...

Streets Section:

% Streets between locations (Edges with Distances as Weights)
% street(Node1, Node2, Distance).
street(1, 2, 0.50, 'Main St').
street(2, 3, 0.75, 'Second Ave').
...

Save node coordinates

Also, get_map saves which node's coordinates on a csv file

Exemple Streamlit

This Streamlit application is designed to help users find the shortest path between two streets using an A* algorithm implemented in Prolog. By printing the best route on a map made with Folium Map