Intro

Here in initial conceptualization of the construction problem, we have outlined the first problem of the series. In this post, we will define the problem in detail and how to solve it.

Problem Definition

Given a layout of a grid world with different elevation levels and reach the desired elevation levels within assigned time and cost constraints using excavators and trucks.

Environment:

• 1 unit of soil is equal to 1 level of elevation.
• There are 20 different elevation levels.
• Elevation difference of neighbouring cells cannot be more than 10 units otherwise it will cause a landslide.
• A landslide will dump the soil to the neighbouring cells until the elevation difference is less than 5 units.
• An excavator/truck can only move to next cell if the next cell is within +-1 elevation from where the vehicle is.
• No two vehicles can share the same space
• A landslide on a vehicle will destroy it hence not allowed.
• A landslide from a cell carrying a vehicle will destroy the vehicle hence not allowed.
• There can be one or more “source” cells where there is infinite amount of soil can be taken from.
• There can be one or more “sink” cell where the soil can be infinitely dumped to.
• Any number of excavators/trucks can be added/removed from environment from an entry/exit point though existance of each will have a cost.
• Each time step is 1 minute and costs 1$.

Agent Excavator:

• Move to a neighbouring cell in 2 minutes.
• Transport a single unit of soil in 1 minute to a neighbouring (including diagonal) cell. Assuming the dug cell doesn’t support any vehicles.
• Reach only +-3 elevation levels from where it is standing.
• An empty excavator weights 1 units of soil. Carried soil effects the weight.
• Each excavator for each time step costs 5$.

Agent Truck:

• Move to a neighbouring cell in 1 minute.
• Carry 10 units of soil.
• Dump the soil in 1 minute to a neighbouring cell up to the elevation level of the grid where it is standing.
• An empty truck weights 1 units of soil. Carried soil effects the weight.
• Each truck for each time step costs 2$.

Given above rules, lets contemplate on the implications:

• Excavation of a cell may need to be done in stages since excavator cannot reach beyond certain elevation.
• To reach a point to excavate, a temporary makeshift road may need to be built to satisfy the elevation difference constraint.
• Such a road may need to have multiple lanes or pockets to allow vehicles to pass each other.
• An arrangement between excavator and truck needs to be done for successful soil transportation.
• So far this is an offline problem, i.e. we can plan the whole operation before starting the execution.

Lets grow into an online problem

Since our initial purpose is to have a robotics project to begin with. Lets add non-determinism, dynamism, partial observability to the problem:

Environment

• Soil can slide from a cell to another with a certain probability even if the elevation difference is less than 10 units.
• A change in elevation level can only be observed if a vehicle is present in 5 cell radius.

Agent Excavator

• Moving to another cell can fail with a certain probability
• Excavation of a cell can fail with a certain probability

Agent Truck

• Moving to another cell can fail with a certain probability
• Dumping the soil can fail with a certain probability

Problem size

This problem could be solved using a search/constraint satisfaction algorithm if it was still an offline problem. Ideally the state space could be defined as the set of all possible configurations of the grid world with time step. The actions can be defined as the set of all possible actions that can be taken by the excavator and the truck. The cost of the actions can be defined as the time it takes to execute the action. The goal state can be defined as the set of all possible configurations of the grid world where the desired elevation levels are reached.

However even then the state space would be huge and the search problem would be non-trivial. Each cell can have 20 different elevation levels, plus numerous vehicles operating in the grid with their own state. For M x N grid alone, number of possible configurations is 20 ^ (M * N).

Divide And Conquer

Finding the optimal solution is not feasible. We need to divide the problem into smaller subproblems and solve them.

We can divide problem into following subproblems:

• Path finding for vehicles.
• Map segmentation.
• Elevation evolution of segment.
• Coordination between vehicles.
• Decision of hiring/retiring vehicles.
• Inspection for environmental changes.

But these subproblems are not independent. For example path finding will require certain elevation levels to be reached (construction of roads) for not just having shortest path between two points (performance) but also for reachability. Similarly elevation levels will decide how many vehicles can operate simultaneously. In return opereration efficiency will effect how the elevation will evolve. (Chicken and egg problem)