Calculating the path between ancient settlements

When investigating ancient civilisations, archaeologists will often know the positions of several settlements in an territory. But in order to understand better how these settlements functioned in relation to each other, they often ask the following question: what are the likely routes that people used when walking between two settlements? Knowing the answer to this question may allow them to draw conclusions such as:

What strategic central locations were there in the territory (e.g. at a crossroads of multiple important paths).

Where there might be other yet undiscovered settlements (on the path between two known settlements).

But even if we know the positions of two settlements, how might we estimate the established route between them? I attempt to answer this question in this short study, during my time at University of Bristol. Using our understanding of the human body, I devise a cost function for walking on hilly terrain. I then build a small program that uses least cost path analysis to compute the path between two settlements over hilly terrain.

See the bottom of the page for a full write up of the study.

The premise

The premise of this study is that over time, a group of humans travelling between place A and B will reach an informal agreement as to the established path. This established path will be the one which minimises the ‘cost’ of walking from A to B. The cost of any particular path will depend on multiple factors such as the gradient, vegetation cover, type of rocks, e.t.c. The optimal path will differ from one person to another due to weight, age, sex, e.t.c. However, eventaully a concensus will be reached and the path that suits the needs of the majority of the population will be used by most people. One reason for this is that over time, the most worn path will be more free of vegetation, and it is easier to follow a path that is clearly marked underfoot compared to heading out across open country.

Assumptions made in the study

A couple of simplifications were made for the sake of a university project.

The cost we are looking to minimise is the metabolic energy for the journey, i.e. humans take the path that uses the least energy to get from A to B.
The vegetation and ground conditions are uniform. This is not true in practice, but in archaeology, we don’t know the historic conditions so this is a valid assumption (Herzog, 2013).
Turning left or right won’t affect the cost of the journey. This is a reasonable assumption for steep terrain (Herzog, 2013).
The path will only depend on the cost of humans walking, and not on that of pack animals such as horses or donkeys.

What is least cost path analysis?

This is an established technique for determining the least cost path between A and B. In order to conduct LCP analysis, it is necessary to first define a cost function. There are two types of cost functions:

Isotropic costs are independent of the direction of movement, and include things like vegetation, soil properties, lakes, rivers, e.t.c. This can be ignored for the purpose of this simple study.
Anisotropic cost depends on the direction of travel, and usually means the cost associated with slope, or gradient of the ground. This is the only type of cost that will be considered in this study.

Implications of the cost objective

As already stated, we are assuming that humans optimse a path over time to minimise the energy cost of walking. From now on this will be abbreviated as Cw. We also assume that the only factor affecting the cost of walking at any one point is the gradient of the ground under foot.

Therefore, to work out the cost of walking any particular route between A and B, we need to do two things:

Determine a cost function that expresses Cw in terms of gradient.
Integrate that cost function over the entire length of the route.

Once we can do this, we have an optimisation problem which can be solved computationally to find the least cost path between A and B.

Finding a cost function

Studying the literature on cost of walking, I found out a few interesting things:

Metabolic cost of walking depends on speed as well as gradient.
There is an optimal walking speed at each gradient which minimises CW.
If we assume that humans optimise their walking speed to minimise CW, there is a known cost function relating CW to gradient (Minetti et al. 2002).
However, when walking downhill at gradients steeper than 10%, humans subconsciously slow their walking speed in order to be more stable, but this increases CW (Hunter et al. 2020).

Therefore, I chose a cost function based on that of Minetti et al. (2002), but adding additional cost at downhill gradients of above 10%. For more detail, see the full writeup linked at the bottom of the page.

Cost function found by Minetti et al. (2002)

Path optimisation in MATLAB

Over complex terrains, an algorithm such as Dijkstra or A* would be necessary to optimise the path. Since the main focus of this study was on developing a cost algorithm, a simplified terrain was used for demonstration purposes. A spur of land between two settlements S1 and S2.

The optimal path between these two settlements will be a compromise between the shortest distance (straight line) and the least gradient (go around the spur staying on flat ground). Therefore, the optimal path calculation is aiming to find the values for a, b, c, and d on the first diagram below.

No complex algorithm is needed for this simplified example. Instead a brute force approach was used. In MATLAB, I constructed paths for for all possible combinations of a, b, c, and d at a resolution of 2°. For each path, I computed the overall cost, by calculating the gradient along the path and integrating the cost function. Of all the 6 million paths tried, the path with the lowest cost was the solution, and is illustrated in the second diagram below.