Shop OBEX P1 Docs P2 Docs Learn Events
Parallel Algorithm for any NP-Hard or well-known Problem — Parallax Forums

Parallel Algorithm for any NP-Hard or well-known Problem

mehri110alimehri110ali Posts: 1
edited 2014-02-19 07:55 in Robotics
I am a computer student and i need a new problem for parallelization.
If you need to send me a sample please

Comments

  • mindrobotsmindrobots Posts: 6,506
    edited 2014-02-19 06:22
    OK, you have an industrial robot that must travel about a set path in a factory setting. As it travels around this path marked by embedded wires in the factory floor, it stops at waypoints indicated by infrared beacons. At each stop, it must measure the temperature, humidity, light intensity and noise levels (for Occupational Health and Environmental regulatory reasons) and report them back to a central computer.

    It also must NOT run into anything that may be in its path. It is a factory setting, so things or people could be in its path for various reasons. If it has to stop, it needs to emit a warning tone and notify the central computer that there is an obstruction in its path.

    Due to the environmental regulations, it does need to travel the entire route in a certain time and make sure it gets to each checkpoint within a certain time limit. To accomplish this, it will need to monitor real time and of course its speed. Speed can be adjust to make sure it arrives at each destination in the correct time frame.

    This is also a hazardous environment and works with chemical that can produce chlorine gas. Since it is roaming the plant with its regular duties, it also carries a chemical neutralization package. If it is instructed by the central computer or detects chlorine gas, it is to navigate to the site of the spill (via gas intensity) and disperse the neutralization chemicals. Once dispersed, it can be remotely operated to evaluate the severity of the spill and any damage.

    There are a number or "Real World" parallel problems in this requirements specification. Is this what you were looking for??

    I don't know what NP Hard is? Some sort of theoretical problem definition?
  • LeonLeon Posts: 7,620
    edited 2014-02-19 07:21
    NP Hard: http://mathworld.wolfram.com/NP-HardProblem.html
  • mindrobotsmindrobots Posts: 6,506
    edited 2014-02-19 07:55
    Sorry, I don't do computational complexity theory, never have, never will. I don't think I've ever had a discussion involving any area of computational complexity theory in my career and from what I've just read at wolfram and on wiki, I never hope I do....my eyes started to glaze over.
Sign In or Register to comment.