Group 31 - Adaptive Matching for Expert Systems

Description

Discrete-event simulation of an expert matching system with uncertain task types, based on the paper "Adaptive Matching for Expert Systems with Uncertain Task Types" by Shah, Gulikers, Massoulié, and Vojnović (2018).

The system simulates two experts processing tasks of two unknown types, comparing the performance of a Random matching algorithm against a Backpressure matching algorithm. Performance is measured by mean sojourn time (time a task spends in the system).

Installation

This project is built on Python 3.12.6. Install dependencies with:

pip install numpy scipy matplotlib

Clone the repository:

git clone https://gitlab.tue.nl/2mbs40/academic-year-2025-2026/assignment-1/Group_31.git

Quick Start and Usage

1. Install dependencies:

pip3 install -r requirements.txt

2. Verify installation (~6 seconds):

python3 -m unittest discover -s tests -v

3. Run all experiments:

python Experiments/run_all_seq.py

Or run individual experiments:

python Experiments/task_4a.py  # Warmup analysis
python Experiments/task_4b.py  # Random policy
python Experiments/task_4c.py  # Backpressure policy
python Experiments/task_4e.py  # Epsilon sensitivity

Project Structure

File / Folder	Description
simulator.py	Core discrete-event simulation engine
experiment.py	Replication management and confidence intervals
experiment_config.py	Parameter configuration
system_model.py	Success probabilities, ψ and φ functions
task.py	Task entity with belief tracking
expert.py	Expert entity
expert_pool.py	Expert pool management
matching_policy.py	Abstract matching policy
random_policy.py	Random task selection
backpressure_policy.py	Backpressure task selection
cell.py	Grid cell container
cell_partition.py	ε-grid partition for backpressure
event.py	Event types (arrival / completion)
fes.py	Future Event Set (min-heap)
system_monitor.py	Sojourn time statistics
Experiments/	Experiment scripts for tasks 4a–4e
Tests/	Unit tests
Dev Testing/	Development and integration test scripts

Class Diagram

classDiagram
    direction TB

    class ExperimentConfig {
        +float lambda_val
        +float delta
        +str policy_type
        +float warmup_period
        +float sim_length
        +float epsilon
        +float a
        +list expert_configuration
    }

    class Experiment {
        +list replication_means
        +run_single_replication(rep_id) float
        +run_replications(n_replications, n_processes)
        +run_adaptive(min_reps, max_reps, target_sig_figs)
        +get_confidence_interval(confidence) tuple
        +has_sufficient_precision(target_sig_figs) bool
    }

    class SystemModel {
        +float a
        +float delta
        +p_success(s, c) float
        +psi(s, zc1) float
        +phi(s, zc1) tuple
    }

    class Task {
        +int true_type
        +float arrival_time
        +tuple mixed_type
        +float departure_time
        +update_belief(expert_type, system_model)
        +sojourn_time() float
    }

    class Expert {
        +int expert_id
        +int type
        +bool is_busy
        +Task current_task
        +isBusy() bool
        +startTask(task)
        +completeTask() Task
    }

    class ExpertPool {
        +addExpert(expert)
        +idleExperts() list
        +getExpert(expert_id) Expert
        +getAllExperts() list
    }

    class Event {
        +int ARRIVAL$
        +int COMPLETION$
        +float time
        +int eventType
    }

    class FES {
        +add(event)
        +next() Event
        +isEmpty() bool
    }

    class MatchingPolicy {
        <<abstract>>
        +match(available_experts, task_pool) tuple
        +chooseExpert(available_experts) Expert
        +chooseTask(expert, task_pool)* Task
    }

    class RandomPolicy {
        +chooseTask(expert, task_pool) Task
    }

    class BackpressurePolicy {
        +chooseTask(expert, task_pool) Task
    }

    class CellPartition {
        +float epsilon
        +cell_of(zc1) Cell
        +all_the_cells() list
    }

    class Cell {
        +int i
        +int j
    }

    class SystemMonitor {
        +float warmup_period
        +list sojourn_times
        +record_task_departure(task, current_time)
        +get_mean_sojourn_time() float
        +get_all_sojourn_times() list
    }

    MatchingPolicy <|-- RandomPolicy
    MatchingPolicy <|-- BackpressurePolicy

    ExpertPool *-- "2" Expert : owns
    FES *-- "*" Event : owns
    CellPartition *-- "*" Cell : owns

    Experiment o-- "1" ExperimentConfig : configured by
    ExperimentConfig o-- "1" MatchingPolicy : uses
    BackpressurePolicy o-- "1" SystemModel : uses
    BackpressurePolicy o-- "1" CellPartition : uses

    Event --> "0..1" Task : references
    Event --> "0..1" Expert : references
    Expert --> "0..1" Task : working on

Loading

Testing

Run all tests locally:

python -m unittest discover -s tests -v

Tests run automatically on every push via GitLab CI/CD. The pipeline also runs flake8 for code style checks.

License

MIT License - see LICENSE for details.