Is multi-device trajectory prediction possible using only classical machine learning?
Any machine learning algorithm could possibly learn a solution once the problem properly defined.
One technique that could aid in learning is to bin the locations. Instead of predicting a specific x and y (and being precisely wrong), predict a more general region. Based on the topological structure of the location, bin similar location points together.
One class of classic machine learning techniques to try would be tree-based, such as decision tree, random forest, or boosted trees.