How We Won a Multi‑Robot Competition: Greedy Scheduling, A* Pathfinding, and Dynamic Window Control

Team Introduction

We are the team "Star and You 1.5m" led by Li Yingtiao from the Northwest division. Our team placed third in the preliminaries, the semifinals, and qualified for the finals.

Task Background

Robots are increasingly used in smart manufacturing, logistics, delivery, and medical fields, creating strong market demand. The competition simulates a multi‑robot environment where participants must solve algorithmic challenges such as optimal task scheduling, collision‑free path planning, and profit maximization by buying and selling items.

Task Objective

Four robots can perform actions like move forward, backward, rotate, buy, and sell to deliver items. The final score equals the amount of money earned; higher profit yields a higher rank.

Interaction Method

The judge program runs at 50 frames per second, providing real‑time state information via standard input and receiving robot commands via standard output. Each frame must be processed within 15 ms; otherwise, the frame is skipped.

Preliminary Round Strategy

We praised the problem for its engineering detail and low entry barrier. The open map allowed us to focus on workbench selection and scheduling without terrain constraints.

Distance‑Based Up‑Down Table

We built a routing table similar to network routing: each workbench stores upstream (producing) and downstream (consuming) workbench IDs, positions, and coordinates. Robots receive a target workbench from the table, move there, execute buy/sell, then update the table for the next step, considering only one segment at a time.

float lineSpeed;
double angleSpeed;
for (int robotId = 0; robotId < 4; ++robotId) {
    float currentX = robot[robotId].x;
    float currentY = robot[robotId].y;
    // ... compute target, orientation, distance, and set lineSpeed based on thresholds ...
}

Collision Detection

Initially we used a simple rule: when two robots collide, we reduce speed dramatically and separate them. Later we studied RVO and ORCA papers and implemented a relative‑velocity based detection using tangent vectors and cross products to decide if a future collision will occur.

int if_collision(int id) {
    int robot0 = id;
    float X0 = robot[robot0].x;
    float Y0 = robot[robot0].y;
    // ... compute relative velocity and check against tangent cones ...
    return -1;
}

Path Finding for the Semifinal

The map contains obstacles, so simple straight‑line movement is insufficient. We used A* on a 100×100 grid to compute shortest paths between workbenches, then applied two cost functions: a corner‑penalty and a wall‑proximity penalty.

int cost1(PathNode* current, PathNode* neighbor) {
    // corner cost
    if (neighbor->row == target_row || neighbor->col == target_col) return 1;
    return 2;
}
int cost2(PathNode* neighbor) {
    // wall cost
    for (int i=-1;i<=1;++i) for (int j=-1;j<=1;++j)
        if (map[neighbor->row+i][neighbor->col+j]==1) return 10;
    return 0;
}

After A* we performed Floyd‑style path smoothing to reduce the number of waypoints.

Dynamic Window Approach (DWA) for the Final

Because the semifinal paths were unsuitable for obstacle‑dense maps, we switched to DWA. The algorithm samples velocity pairs (v, w) in the robot’s velocity space, simulates short trajectories, and evaluates them with a weighted cost function that includes orientation alignment, obstacle distance (using an Euclidean Distance Transform map), robot‑robot distance, and speed.

RobotState* cal_control(RobotState* cur_state, vector<SimplePathNode*>& target) {
    // sample v and w within dynamic window, simulate, compute costs, select best
    cur_state->change_v = best_v;
    cur_state->change_w = best_w;
    return cur_state;
}

Euclidean Distance Transform (EDT)

We generated an EDT map to obtain the distance from each free cell to the nearest obstacle. The transform consists of two passes per row (left‑to‑right and right‑to‑left) followed by a column pass that computes the minimum combined distance.

class EDT {
private:
    int Gmap[100][100];
public:
    void get_edtmap() {
        // first pass: horizontal scans
        // second pass: vertical scans
    }
};

Avoidance Implementation

For narrow corridors we expanded each robot’s path by one grid cell on both sides, then used bitwise maps to detect overlapping sections. When robots approach the same overlap point, the one farther away slows down, allowing the nearer robot to pass.

if (meet[robotId][0] != -1) {
    // compute distances to meet point, decide who slows down
    if (line_v*line_v/2/15*5 > meetDis && meetDis > meetMinDis) lineSpeed = 0;
}

Radar Enemy Detection (Final Round)

The radar provides 360 distance measurements per frame. By rotating the robot’s orientation and converting polar coordinates to map cells, we identify non‑wall, non‑ally points as enemy robots. We keep a list of enemy positions, update them across frames, and assign each robot a unique target.

for (int idx=180; idx<540; ++idx) {
    int radarIdx = idx % 360;
    float line_dis = robot[robotId].radar[radarIdx] + 0.3f;
    // compute world coordinates, check map for obstacles or allies
    // store nearest enemy point
}

Final‑Round Strategies

We introduced a two‑team mode (red vs. blue). Blue robots have higher pulling force, red robots are faster. We added laser‑radar to locate opponents. Two blue strategies were implemented:

Steadfast Guard : robots stay near designated workbenches, wait for enemy deliveries, then push them away.

Hunt Mode : robots actively chase enemy robots until they are cornered.

Both strategies use the same avoidance logic with added forward‑blocking zones and speed reduction when robots get close.

Scheduling Adjustments

We tracked delivery counts for high‑level workbenches (4, 5, 6) and prioritized robots to fetch raw materials for the least‑served workbench, balancing production.

int curtype = idtype[robot[i].wb_target_id].first;
int lasttype = idtype[robot[i].last_wb_target_id].first;
if (curtype==4 && lasttype!=4) rbtarget_num[4]++;

Post‑Competition Reflections

The competition taught us valuable lessons about algorithmic robustness, memory management (our A* and DWA loops leaked memory), and the importance of quick‑turnaround debugging. Future work includes tighter integration of radar data with RVO, better map pruning, and more sophisticated expectation‑based scheduling.

Conclusion

Through a combination of greedy distance tables, custom collision detection, A* with cost tuning, DWA with EDT‑based obstacle costs, and radar‑driven enemy tracking, we achieved a top‑three finish. The experience reinforced that practical robotics problems require both solid theoretical foundations and careful engineering.