0
$\begingroup$

I'm interested in characterizing the complexity of a decision problem related to path planning. For instance, consider the following problem: Given the current location and battery charge of an outdoor robot, does a trajectory exist such that the robot reaches a goal region without running out of energy? enter image description here

I assume the outdoor environment is made of different types of terrain each affecting the robot's energy consumption differently (ex: grass, sand, mud, etc.). The robot can also visit charging stations along the way, but these stations are only operational at certain times of the day. As such, the configuration space of the overall planning problem has 4 continuous dimensions: the 2D position of the robot in the map, the time of the day and the robot's energy level. I assume that the robot's state is fully observable, the state dynamics are deterministic, and the entire map & charging station schedules are known ahead of time.

Intuitively, this seems like a hard decision problem. However, I'm struggling to find a valid reduction from a known NP-hard or NP-Complete algorithm. My best lead at the moment is the generalized mover's problem, which is PSPACE-hard (which implies NP-hard). The piano mover's problem is a similar formulation. However, there is a difference between the mover's problem and my problem: the mover's problem assumes a goal state (instead of a goal region). Does this matter?

Is the mover's problem an appropriate NP-hard problem to reduce to my problem? If not, what other known problem could I reduce from?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

I see no reason to expect this to be NP-complete. If you discretize the state space, it is solvable with dynamic programming (in fact, reachability analysis on the state space suffices).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the reply. However, couldn't you use the same reasoning (discretize the state space & use DP) for the piano mover's problem? In that case, why is it considered to be PSPACE-hard (which implies NP-hard)? As the discretization resolution increases, isn't the problem becoming intractable? $\endgroup$
    – olamarre
    Commented Sep 16, 2022 at 14:22
  • $\begingroup$ (or are we concerned with intractability only when the dimensionality of the configuration space increases?) $\endgroup$
    – olamarre
    Commented Sep 16, 2022 at 14:28
  • 1
    $\begingroup$ @olamarre, I am not familiar with the piano mover's problem, but that link states "The main problem is that the dimension of ${\cal C}$ is unbounded", whereas in your case the dimension is 4. $\endgroup$
    – D.W. ♦
    Commented Sep 16, 2022 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.