Good evening everyone,

I have a question that I am having a bit of trouble formulating properly and thus it is making it complicated to look up literature on the subject. What I am looking for is a name for a more general problem of the same nature, and I think it will have something to do with the title of this question, dynamic path planning and sorting.

Before getting into the details, I'll try to summarize the question as best as I possibly can:

Attempted Summary

In a complete and weighted graph, which algorithm(s) should be used to continuously obtain a path which maximizes the reward obtained from visiting vertices if the rewards are dynamic and thus constantly changing?

And now, a bit more context.

Problem Statement

Suppose we have a robot:

  • The robot is capable of autonomous movement
  • It is fitted with several sensors
  • The robot must patrol a set of locations L and gather data using its sensors at all of the li ∈ L
  • Some locations are more interesting than others, and may be worth visiting more frequently. What makes these locations "more interesting" is that data taken from these locations have a higher variance than the data taken from other locations. Also, it is important to take into account the time since the location was last visited. The longer it has been, the more desirable it will become to visit.

The goal is to properly schedule the order in which the different locations should be visited so that we can both maximize the information gain and minimize the energy expended by the robot, e.g: the distance traveled. We can assume the robot can move freely from any point and to any location, not just from location to location. Also, the robot must gather data continuously for a period of time T, so the scheduling has to be done more than once.

My view

To me, it looks like this problem can be modeled as a graph. The vertices represent each of the locations that the robot must visit, and the edges have a cost associated to them which represent the distance that must be traveled. I believe the robot itself can also be modeled as a vertex in this graph, which has edges connecting it to every single other location. We can assume all locations are also fully connected between each other, since the robot can go from li to lj such that ∀ i, j ∈ L, however some of these pairs will not be desirable given the distance.

So we are trying to minimize energy expenditure while maximizing information gain. This part sounds like an optimization problem. If I can model the information gain or "reward" obtained from visiting each vertex, taking into account factors such as arbitrary importance of the vertex and variance, it might make sense to use a classical pathfinding algorithm, however I am not too sure how these algorithms behave when used against vertices whose rewards change over time (the overall reward of a vertex will be affected by the amount of time that has passed since it was last visited).

I have also thought about modeling this as a linear programming problem, however I am not quite sure how to obtain a sorted set using this approach (of course I can get the best and worst locations to visit, but what about the order of the rest?)

Thank you for your suggestions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.