Pathfinding on PLC

Has anyone got experience implementing a pathfinding algorithm (like AStar or Dijkstra) on a PLC?

I'm a student and considering this idea for a final project:

Given a fluid network, with many pumps, valves, tanks, and outlets, the operator should have an interface (HMI) to select where they would like fluid to be pumped from and to.

The system would then automatically, and not via pre-programmed routes, determine the best way to get the fluid pumping and configure all of the valves and pumps appropriately. This would enable features like automatically rerouting around broken components. It would also mean that when the fluid network is changed (new pipes, valves, pumps, etc. added), they just needed to be included in the PLC's data, and it will automatically figure out how to use them.

I'm pretty sure this isn't a normal PLC task, but has it been done? How possible is it?

Theoretically possible, probably. I'm willing to bet that some large DCS systems sell routing solutions as an option.

As for implementing it yourself, maybe? I just looked up Dijkstra on wikipedia, and the psuedocode looks rather short. The trick will be that most PLCs don't really support full object oriented programming, so you would have to implement most the data structures yourself out of simple arrays. Out of the standard PLC languagues, I'd recommend SCL. Most people, (especially in this forum) use ladder whenever possible, but SCL is usually better for algorithmic coding.

One other thing to consider for your project is that in a practical system, there will probably be multiple things getting pumped at the same time, so it may want to select optimal pathing given multiple sources/destinations. It may also want to take into account that many chemicals leave residue as they flow through pipes, and they must either be flushed afterwards before they can be used again, or the beginning of the next flow must be considered contaminated.

I know that is noticeable in oil refineries, as they switch from refining one kind of crude to another. Different types of crude oil have different refining properties, and things get blurry during a changeover period.

I don't know if it's been done in a PLC. It would be quite doable though I wouldn't want to do it with a PLC that didn't support a structured text language and array data types.


At least two commercially available packages are available that offer automatic routing. They are Route Control by Siemens and Movement Automation by Honeywell. I'm pretty sure these are workstation-based packages.

I wrote a batching system once for a process that clean/coated/sealed medical devices. Each step had a Source and Destination with up to two setpoints that could be And/Or to complete the step. Time was a separate setpoint for each step.
A 'Source' could be chemical (A) and the system would look at the tanks available and determine which one to use based on several factors of each tank (Level, age, temperature etc). 'Destination' could be Return to source, drain, reclaim etc. Setpoints could be Flow rate, Flow total, Temperature etc.

It worked out very well for them. But I have never used it again after that job. And that was about 14 years ago.

One other thing to keep in mind is that most PLC code is cyclic, and this routing algorithm will probably take a long time to execute (big FOR loops). If the algorithm is only run occasionally, but runs to completion in one go, it could double or triple the scan time of the rest of the PLC program.

It would be better to either have the algorithm be lower priority than the rest of the PLC code, or to have it run slowly over a period of scans. It is fairly common in PLCs to have looped algorithms run one loop (or a few loops) each scan cycle, to avoid the impact to the rest of the PLC code of running through the whole thing at once. This is ESPECIALLY true if you are looking at nested loops. It may make sense to run the whole inside loop, but only increment the outside loop once each scan.

I would try a different angle than moving fluids. Its just not practical in the real world. Equipment is different, mechanics of a system often determine what we can program and what we can't. If the piping/tanks have to be cleaned, that introduces additional complexity, and lets not forget, in the real world this approach would be extremely prone to human error much more than a defined program sequence.

Obviously for a school project, have at it.

A real-world example where I have seen a pathfinding algorithm is on a large plating line, where multiple products and multiple recipes would be introduced at any given time. The pathfinding algorithm was then used to determine the most efficient route through the line, given work that is in progress and what the new part's recipe required. It was pretty impressive once it was up and running, however the bulk of the pathfinding logic was all done at the SCADA level (Using VB scripting) with a lot SQL database interaction as it would store all the data that tracked all the work in progress as well as storing all the timing/routing information required. It was a significant undertaking.

I'll summarize that system.

- 30 different stations a part could get treated at. Each station was essentially a dipping pool of chemical or a rinse station.
- Many stations where of the same type. 4 for 'rinse', 2 'final rinse', 6 'gold plating', 4 'nickel platting', 8 - 'chemical cleaning', bunch of other stations I just can't remember right now.
- Each part had a recipe which defined the chemical treatment process, and time required at each station.
- 2 loading stations, 2 unloading stations.
- 8 hoist/trolleys to lift and move parts.

So when loading a new part into the system the system would recall the recipe information; compare the required station treatments to the the stations available; compare them to the stations required by the parts currently in the system; create a schedule for the quickest path through the system (this was NOT a First-In-First-Out, completely flexible). Oh, it also accounted for the time it took the hoist/trolley to lift and move the parts to the next station. The system would load up with ~ 10-12 parts in process. The system would also understand when it had to 'wait' before loading an additional part because the system was simply maxed out. You would get a count down timer at the loading station indicating when it would be put into the system.

With all of that said, if you can come up with a contained system, that would need to be dynamic and base it on a part recipe rather than operator configuration, it's a bit more realistic and applicable. However, you probably aren't going to do something that complex in a PLC, you would have to simplify it down quite a bit. You can do a lot with Structured Text in a PLC, I wouldn't even think about doing this in ladder.

EDIT: The system would also re-schedule everything if something went wrong. Basically every time a part moved from one station to the next, the path/schedule was re-computed and updated. Have no idea what algorithm was used, I was lean and green at the time and hoped I could learn half the stuff the guy who programmed had forgotten over the years.

Thanks for all of the feedback. It's really interesting hearing the past projects that you have worked on or heard of.

It seems like the consensus is that it's doable using structured text, though I'll need to be aware of what programming features are / are not available in that language, especially coming from a C++ background.

I think mk42's suggestion about breaking up the algorithm's main loop into parts so that it runs over many consecutive scans, rather than all at once, is a great idea. I was just about to ask if PLCs support any sort of "background" / non-realtime tasks, but I think that's the solution.

There were a lot of good suggestions about what the limitations of this system would be / features that it should have. Since this is a student project, we can ignore a lot of that and focus on just getting the core technology working. Obviously, if were to be implemented outside of research, we'd have to go waaaay back to square one and look at all of the requirements of a real system.

mrandy said:

Has anyone got experience implementing a pathfinding algorithm (like AStar or Dijkstra) on a PLC?

I'm a student and considering this idea for a final project:

Given a fluid network, with many pumps, valves, tanks, and outlets, the operator should have an interface (HMI) to select where they would like fluid to be pumped from and to.

The system would then automatically, and not via pre-programmed routes, determine the best way to get the fluid pumping and configure all of the valves and pumps appropriately. This would enable features like automatically rerouting around broken components. It would also mean that when the fluid network is changed (new pipes, valves, pumps, etc. added), they just needed to be included in the PLC's data, and it will automatically figure out how to use them.

I'm pretty sure this isn't a normal PLC task, but has it been done? How possible is it?

Click to expand...

There are modules for PLC's that will run C and other languages. Prosoft makes one for C that I have used many times and there are lots of A*implementations in C already.

I would use that as a starting point.

PBuchanan said:

There are modules for PLC's that will run C and other languages. Prosoft makes one for C that I have used many times and there are lots of A*implementations in C already.

I would use that as a starting point.

Click to expand...

PBuchanan does make a good point, there are options out there for programming a PLC in C, or other languagues. There are multiple manufacturers of PC based PLC systems (which might be able to natively handle C code), and some manufacturers of pc based co-processors to fit in the main PLC rack. If you have existing sample code, it would probably be much faster to convert it into one of these. The downside is that the implementation wouldn't be nearly as applicable to multiple vendors or applications.

mrandy said:

It seems like the consensus is that it's doable using structured text, though I'll need to be aware of what programming features are / are not available in that language, especially coming from a C++ background.

Click to expand...

Although Structured Text is theoretically standardized as part of IEC 61131-3, every manufacturer implements it differently. In general, they support arrays and indexing through them, as well as basic logic constructs like if/then, for/next, case/select, and do/while. Did you ever use BASIC to program your calculator, or in grade school? Its probably about at that level, with the slight change of a Pascal like syntax. It MIGHT support pointers (depending on vendor), but don't count on any sort of class based object oriented shenanigans.

Basically, its what a bunch of non-programmers decided was a good idea in 1993, plus a couple vendor based tweaks.

mrandy said:

I think mk42's suggestion about breaking up the algorithm's main loop into parts so that it runs over many consecutive scans, rather than all at once, is a great idea. I was just about to ask if PLCs support any sort of "background" / non-realtime tasks, but I think that's the solution.

Click to expand...

Again, different vendors support different options, but there a a few things that many have in common. The most basic is the typical synchronous PLC scan, or "continuous task". The program gathers the inputs, runs the code, writes to the outputs, then starts over again. The code in the continuous task is typically the lowest priority. When it is interrupted, it pauses, and typically starts up where it left off once the higher priority code is finished. In most of the plc programs I see, all of the programming is done here, and priority levels or other types of tasks never get involved.

Most PLCs also have "Cyclic tasks" which are executed at a certain interval. These are higher priority than the continuous task, and interrupt it.

You could structure your code with the main code in a higher priority cyclic task, and then letting the algorithm run in the continuous task in the background. The other option is what you already said, where you run it piece by piece each scan. I would say both methods are valid, and which is better depends entirely on the performance requirements.

Path finding should not be done on a PLC. It would consume too much CPU time and may cause stack over flow faults due to the recursive nature of searching. If I had a need for path finding I would get a Raspberry PI 2 or Beagle Bone Black. I wrote path finding code long ago so I have code that works. I would get a modbus TCP driver to communicate with the PLC. I probably have that laying around somewhere too.

Shouldn't be done? Or just needs to observe CPU time and memory limits?

Neither of the algorithms mentioned are recursive, so don't worry about that causing a stack overflow.

mrandy said:

Shouldn't be done? Or just needs to observe CPU time and memory limits?

Neither of the algorithms mentioned are recursive, so don't worry about that causing a stack overflow.

Click to expand...

It shouldn't be done. I am not going to say it can't be done. There are all sorts of things that can be done like motion control, fuzzy logic, neural nets, chess etc on a PLC but they are painful to implement and never run as well as they can on a PC that isn't limited like a PLC.

If you know how big the grid will be then you can allocate an array big enough for all the modes. This way you won't have to use dynamic memory allocation. I don't know of any PLCs that have a malloc() or free() type of functions.

The algorithms search can be recursive or not. I used a recursive version that kept a little data on the stack instead of allocating a heap or big array.

You can always flatten a recursive algorithm, it's not that beautiful as it would be when recursive, but you can do it.
If you have a well defined system where you know how deep the complexity would be, you can check the limits of the PLC and if you can do it inside the PLC.

I've done a parser and interpreter for simple arithmetic formulas inside a S7 plc, using recursion for parsing the given formula. The S7 allows allows 16 sub-calls inside a call. Every expression needs 5 sub-calls, and each expression in parentheses needs another 3. So you have to define your limits if this is enough for your application.

I always try to avoid a using a separate computer for such calculations, as long it's possible to do inside the existing PLC. Or choose a PLC which can do this. With Beckhoff TwinCAT PLCs for example, I know you can do many complicated algorithms in background written in C++/Matlab.

So what's the argument for using separate hardware, rather than the existing PLC? If I'm understanding this correctly it's agreed that there aren't any technical hurdles that would prevent the completion of this project. While an external processor + interface would certainly bring more computing power for other, larger projects, I don't see where it would add any value here, and would certainly increase the cost of the project.

If you use a PC for example, you can simple copy&paste any existing code you find in the internet (there should be many examples) into your application. The only thing you have to spend brainwork in, is how to exchange the data with the PLC.
If you want to program this inside the PLC, you have to implement the algorithm to your system that you use (you won't find any complete coded solution), and have to check its limits.
The limits on the PC are also there (the Turing machine has no unlimited tape to store data), but no one thinks about this, as in a real application you won't reach the limits. Especially for Dijkstra, it's a NP complete, but not a NP hard problem.