In the competition, you will be provided with: a map, a route planner, start and destination locations, and a user model consisting of personal routing preferences. We assume the user model to be correct for the purposes for the competition.
From these components, the optimal route for this user can be computed - the fact route.
You will also be provided with a different route from start to destination - the foil route that a user expected to be optimal.
The user's question is: Why is the fact route optimal for me, and not the foil route?
The explanation we are looking for is a counterfactual map: A map that is as similar to the original map as possible, in which the foil route would be optimal. The differences between the counterfactual map and reality serve as an explanation for the optimality of the fact route, as they show what exactly is "missing" to make the foil route optimal instead.
A foil route is defined as "optimal" for a given counterfactual map if it is returned by the route planner for this map and the unchanged start, destination, and user model. The definition of "similar" is a graph distance metric, defined below. The changes to the original map that are allowed to create counterfactual maps are called map operators and described below. Counterfactual maps that have an optimal route very similar to, but not quite identical to, the foil route can still be valid solutions; we describe the optimization problem as constrained by a maximal distance between these routes, with the route distance metric defined below.
User model and Router:
We will provide multiple user models, each of which will influence the routing results. The competition itself will provide new user models to the participants.
Each user model is defined by the following parameters:
min_sidewalk_width: Minimum acceptable sidewalk width
max_curb_height: Maximum acceptable curb height
crossing_weight: A parameter that indicates how dispreferred crossings are
walk_bike_preference: One of {Walk, Bike} indicating the preferred mode of traveling: on footpaths or bike paths
weight_bike_preference_factor: A parameter that indicates the strength of the preference specified by walk_bike_preference
The user model is used by the route planner in the following way: Edges that are violating the min_sidewalk_width or max_curb_height are excluded from the map before routing. The length of edges is modified by the parameters crossing_weight and walk_bike_preference_factor for the purposes of routing.
We will use a classic path planning algorithm (e.g., Dijkstra's algorithm ) as a router. The heuristic function is based on edge attributes such as curb height and width, considering the user model.
Graph operators:
Participants should only modify the following attributes, adhering to the graph operators:
Width (numerical): Modify the value of the width of one edge.
Range of width is [0.6 m, 2 m]
The key name of width in the dataframe is "obstacle_free_width_with_float"
Curb height (numerical): Modify the value of the curb height of one edge.
Range of curb height is [0, 0.2 m]
The key name of curb height in the dataframe is "curb_height_max"
Path type (categorical): Modify the value of the path type: "walk" or "bike".
You are only allowed to change from "walk" to "bike" or from "bike" to "walk".
The key name of path type in the dataframe is "path_type"
If the operation violates the above constraints, such as being out of bounds, the value modification should fail.
You should not modify other attributes, or add or remove any edges from the graph.
We will provide a template to implement these operators.
Graph distance metric:
Route distance metric：
The difference between two routes is based on the weighted common edge rate:
We provide multiple maps, corresponding foil routes, a route planner, and user models as the training dataset. During the evaluation phase, all submissions will be evaluated using a separate test dataset (e.g., different maps, foil routes and user models).
Map: A DataFrame with multiple attributes.
Foil Route: A DataFrame representing the edges of the route with start and destination locations.
Route Planner: Implements the Dijkstra algorithm (provided). Its heuristic function is based on edge length, weighted by the user model and the above attributes.
Evaluation Criteria:
Submission requirements:
For all submissions, we will run the code on a fixed device with the same computational budget, limited to 5 minutes per pair of map and foil route. Ensure that your code is fully self-contained, includes all necessary dependencies, and can execute without internet access.
The computing environment will be: 64 Intel Xeon CPUs with an NVIDIA A100 GPU and 120 GB memory.
Submissions must be optimized for efficiency within this constraint. The output of your algorithm for each data pair <map, foil route> should include:
The final modified graph/map
The list of graph operators applied to achieve the modification
Please follow the templates we provide to store and evaluate your results.
You can find the datasets and codes in this GitHub repository: https://github.com/HcPlu/CRC25
Note: In addition to the code base, each team needs to submit a report of 2 - 4 pages in the default IJCAI 2025 template, following academic standards, including an abstract, related literature, and a description of the work performed.
If you encounter any problems with the dataset or code, please let us know: crc25ijcai@gmail.com
In order to ensure a fair comparison between participants we expect all code to be written in Python, with the use of a limited set of standard libraries such as NumPy, Pandas, geoPandas, NetworkX, math, Pickle, and Torch.
We expect the submissions to be open source. Teams will be responsible for their own repository maintenance. We will publish the competition and related code, announce the results, and link to the repositories of all participating teams in our website.
The code is to be submitted by sharing a Github repository with the organisers before the submission deadline. The organisers will check as soon as possible whether the code runs. If it does not run, the participants may still correct this, if and only if the submission deadline has not been reached. At the submission deadline, the code will be frozen and entered into the competition. The participants may choose to make their repositories public at this point, or wait until after the results are announced. By entering the competition, however, the participants agree to open-sourcing their submissions.
According to the competition rankings, we will award certificates to the high-performing teams and invite them to present their work on-site at the IJCAI 2025 conference.