Just a set of experiments/improvements on the TSP model.

Vectorize Training (make_vec_env)

The first goal was to speed up training. The simplest way to do this is to use multiple environments at the same time. This will batch the policy inference. Since the game is so simple, that is probably(?) the bottleneck. It also helps with training by reducing correlation. With 16 games occurring at the same time, we’ll get a wider range of varying game states to train on each training step, so we don’t rabbit hole.

env = make_vec_env(VRPEnv, n_envs=16, seed=config.SEED, env_kwargs={"size": config.SIZE})

hours: Discrete(25) -> Box(float, (1,))

Modeling hours as a Discrete(25) actually models the input as 25 unique inputs (25 binary inputs, but they’re actually floats afaik). So instead we can model hours as a single float (hour/24).

This didn’t end up making a different in final scores, but I left it in.

n_steps 2048 -> 256

The final scores after vectorizing the training were much worse. It looks like it was due to fewer policy update cycles. Training doesn’t happen after each step, but is instead batched after a set of runs. But due to the vectorization of n=16, we had 16x less total training update batches in the training runs. So by decreasing the number of steps between training, we can improve faster (when n=16).

MaskablePPO

The model spends a lot of time learning about impossible/invalid actions such as DO_TASK on tiles that have no tasks, or trying to move off the map.

So instead we can mask those actions to prevent the model from selecting those. This doesn’t actually “teach” the model that they’re bad actions, it just prevents them from being selected so we can spend more time exploring valid states.

Implementing was pretty simple, just a list[np.bool_] for each of the actions.

torch.set_num_threads

Training was again slow, and it seems that creating a separate thread for each env is slower than just keeping all the envs in one thread. Again simple, just torch.set_num_threads(1).

agent_position as one-hot instead of position tuple

Before trying CNNs, I figured I’d try to instead represent position as a one-hot grid. It didn’t improve much. But useful before implementing the CNN.

CNN

When using the flattened grids, the model has to learn how they are spatially connected. The idea with using CNNs is to hopefully preserve that spatial awareness. Implementing CNN in the existing architecture involved implementing a BaseFeaturesExtractor.

I have no intuition when it comes to building models, so the LLM recommended:

self.cnn = nn.Sequential(
    nn.Conv2d(2, 16, kernel_size=3, padding=1),
    nn.ReLU(),
    nn.Conv2d(16, 32, kernel_size=3, padding=1),
    nn.ReLU(), 
    nn.Flatten(),
)

self.projection = nn.Sequential(
    nn.Linear(32 * size * size + 1, features_dim),
    nn.ReLU(),
)

Tomorrow I hope to learn more about why these parameters were chosen.

The CNN didn’t show much of an improvement on small grids.

Large Grids with density (.2)

The grid has a task density of roughly .5, which means that pathing isn’t quite as important. You can just go in some direction and pick up a task. By reducing the density of tasks I’d hope that the model would have to learn more intelligent pathing.

Results:

Density = .5
(CNN)
[+] Average scores over 100 games: PPO=9.87, Greedy + 2-opt=10.87
(MLP)
[+] Average scores over 100 games: PPO=7.82, Greedy + 2-opt=10.84

Density = .2 
(MLP)
[+] Average scores over 100 games: PPO=4.92, Greedy + 2-opt=8.00
(CNN) 
[+] Average scores over 100 games: PPO=6.77, Greedy + 2-opt=7.57

Density = .05
(MLP)
[+] Average scores over 100 games: PPO=1.79, Greedy + 2-opt=3.76
(CNN)
[+] Average scores over 100 games: PPO=3.62, Greedy + 2-opt=4.05

So CNN seems to do better in all cases, and does very well with low density. It is cool to see it is pathing pretty well:

CNN, Density=.05, Rounds=500_000 Size=10

MLP, Density=.05, Rounds=500_000 Size=10

CNN, Density=.05, Rounds=500_000, Size=10

Next Steps

Next I want to learn more about CNNs. Then I think I’ll finish the Hugging Face section on Multi-Agent models, and start converting the environment to a multi-agent vehicle routing problem.