Let's Build a Problem (as if we don't have enough of them)

Intro

My recent focus has been on exploring various topics of robotics, particularly the architectural design of robotic systems. However, the work environment lacks the flexibility to experiment with, test and validate new concepts effectively. Thus, I require a simplified scenario — a toy example that presents sufficient challenges to hone my skills.

I envision the ideal problem to possess the following attributes:

Multi-Heterogeneous Agents: Involving one or more agents with diverse capabilities collaborating on a task.
Decentralized Operations: Absence of a centralized planning authority; agents receive an abstracted problem definition and autonomously determine their solutions.
Dynamic Environment: Factors beyond the agents’ control constantly alter the surroundings.
Nondeterministic Elements: Actions do not always yield expected outcomes.

Consequently, the agents should be capable of:

Planning and executing individual tasks.
Communicating with other agents.
Reacting to environmental changes and other agents.
Managing errors effectively.

Initially, I considered utilizing existing benchmark problems in robotics. However, many are too narrowly focused. For instance, while robot soccer showcases teamwork, it lacks significant agent heterogeneity and an open, dynamic world. Similarly, navigation, search and rescue, and exploration/mapping problems primarily emphasize motion planning/control rather than behavior/task planning.

My alternative consideration was to develop agents for a game.

Dota 2 is a great candidate, and it satisfies many criteria listed above (except maybe nondeterminism). However the lack of control over the game environment and the complexity of the game itself makes it hard to simplify problems to tackle in intial steps. Additionally, the game is horizontal scalable i.e. increasing complexity involves adding more agents with similar capabilities rather than addressing larger or diverse challenges.

Problem Overview

I propose a scenario involving a neighborhood construction company where the task is planning and building houses and amenities. A quick online search revealed three primary types of roles in construction:

Creative Roles: Engineers, Architects
Oversight Roles: Managers, Schedulers, Inspectors
Labor Roles: Carpenters, Electricians, Ironworkers, Joiners, Plumbers, Painters, Pipefitters, Roofers, Welders, Delivery Personnel (Truck Drivers), Machinery Operators

In this scenario aach agent could undertake at least one of these tasks.

Given my limited knowledge of construction project planning and execution, I will outline a logical waterfall sequence of actions:

Engineers and Architects collaborate on an optimized design.
Managers create a schedule, oversee execution, and ensure timely, cost-effective, high-quality project completion.
Laborers execute assigned tasks punctually and with high quality.

Lean Execution

In addition to these,at a later step I would imagine the capability of “lean” project management (see Lean Manufacturing, Lean Startup) would be a great addition. Which would involve:

Identify success critia
Identify uncertainities
Develop a hypothesis
Plan a smallest livible naighbourhood where the hypothesis can be tested as well as using previously verified knowledge and strong assumptions
Executed
Get feeback
Go to step 2.

Agent Characteristic

To formulate a planning problem, each agent will possess distinct characteristics:

Laborer:
- Hourly wage
- Error rate in work (percentage)
- Work speed (coefficient)
- Time constraints (work hours)
- Performance metrics (combination of above factors) affected by inspection/management
- Performance metrics (combination of above factors) affected by oversight presence
Overseers:
- Hourly wage
- Error detection rate (percentage) (quality of inspection)
- Inspection speed (percentage of work time: e.g., 1% enables inspecting 100 hours of work in 1 hour)
- Planning/scheduling speed (coefficient)
- Planning/scheduling quality (time threshold + optimization function)
- Hiring accuracy (coefficient, error rate in laborer evaluation)
Engineers & Architects:
- Hourly wage
- Planning/scheduling speed (coefficient)
- Planning/scheduling quality (time threshold + optimization function)

Agent Performance:

Key performance parameters for each role:

Laborer:
- Negative impact: Deviation from expected job completion time (percentage)
- Negative impact: Number of errors
- Negative impact: Wages
Overseer:
- Negative impact: Time taken for overall management (percentage)
- Negative impact: Total project cost
- Negative impact: Total errors
- Negative impact: Wages
Engineers & Architects:
- Positive impact: Satisfaction of criteria (weighted per criterion)
- Negative impact: Project completion time
- Negative impact: Wages

However, each job can be divided into smaller tasks for parallel execution. For example, designing the entire project does not need to precede creating a basic neighborhood layout, enabling excavators to commence digging.

Environment

A (initially) grid world with a regular tiling pattern. It can be square or in order to increase neighbors may be hexagon [0].

Constructible structures include:

Residential buildings
Parks
Shops
Schools
Hospitals
Police stations
Fire stations
Roads

Map properties encompass:

Terrain elevation
Existing roads
Pre-existing structures
Vegetation
Bodies of water

Initial Steps

To avoid overcomplication, I will halt further planning and start problem implementation. Beginning with a simple grid world and a single agent, I will gradually introduce additional agents and environmental complexities.

Problem #1: Generating layout

First task generating a simple problem definition: Given a layout of a grid world and required number of structures, create a layout to maximize resident satifaction, generated revenue, while minimizing construction costs. Resident satisfaction is function of: * house size * closeness to various facilities. * neighbouring same/different class buildings * distance to nearest road * distance to nearest water body * distance to nearest vegetation

What we defined is an optimization problem, which can be solved using a search or a constraint satisfaction algorithm.

Problem #2: Ground work

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 has +-1 elevation from where the vehicle is.
Agents:
- Excavator:
  - Excavator can move to a neighbouring cell in 2 minutes.
  - Excavator can transport a single unit of soil in 1 minute to a neighbouring cell. Assuming the dug cell doesn’t support any vehicles.
  - Excavator can reach only +-3 elevation levels from where it is standing.
  - Empty excavator weights 1 units of soil. Carried soil effects the weight.
- Truck:
  - Truck can move to a neighbouring cell in 1 minute.
  - Truck can carry 10 units of soil.
  - Truck can dump the soil in 1 minute to a neighbouring cell up to the elevation level of the grid where it is standing.
  - Empty truck weights 1 units of soil. Carried soil effects the weight.

Given the above two, second one is a more interesting problem to solve. It involves planning and execution of tasks in a dynamic environment. So I will start with the second problem.

See: Ground Work Problem #1

Implementation

I am very comfortable with modern C++ and Python so will use a combination of both: Quick prototyping of python and fast/parallel execution of C++ with wrappers.

Let’s get down to business.