Algorithm to compute fastest method of collecting $k$ re-spawning items which spawn at $n$ specified points

Question

Let $V = v_1, \dots, v_n$ be the locations the items can spawn at, and let $U = u_1, \dots, u_k$ be the current positions of the items. We will assume a new items spawns instantly every time we collect an item, so there are always $k$ items (Assume uniform distribution for spawn location). Let $w$ be the current position of the character. Then $S = (V, U, w)$ is the state of the game.

Assume the character can move at a constant speed, so the time metric we care about is proportional to the distance between two points.

Essentially I want a function $\text{bestItem}(S)$ that tells me which item in $U$ to go to first to maximize the number of items I collect per hour.

This seems similar to shortest path on a clique with weighted edges, but it doesn't stop after one step. Or a traveling salesman problem where the traveling salesman doesn't know all the locations he needs to visit from the start.

Is there a name for this problem? I am curious if it is already solved, and how good the greedy method of just always taking the nearest item is compared to the optimal method. Or the method of computing the shortest path through the points of $U$, and updating it after some number of spawns.

Has anyone worked with this type of problem and point me at some reading material? My interest is inspired by video games which have mechanics like this.

Thanks.

Answer 1

This is essentially the disk scheduling problem in a general metric space. You can read about it in the paper Reordering Buffers for General Metric Spaces for example:

Abstract: In the reordering buffer problem, we are given an input sequence of requests for service each of which corresponds to a point in a metric space. The cost of serving the requests heavily depends on the processing order. When serving a request the cost is equal to the distance, in the metric space, between this request and the previously served request. A reordering buffer with storage capacity k can be used to reorder the input sequence in a restricted fashion so as to construct an output sequence with lower service cost. This simple and universal framework is useful for many applications in computer science and economics, e. g., disk scheduling, rendering in computer graphics, or painting shops in car plants.

Alternatively you could read the section on disk scheduling algorithms in any operating systems textbook or look at some algorithms that reduce seek times here, they apply to the line metric space mostly but it should give you a general idea.