Two sentences come out of one piece of advice, pointed in opposite directions. Ho andato a Roma is the advice not applied where it works. Sono viaggiato tutta la notte is the advice applied where it does not. The advice is that verbs of movement take essere, and it gets a great deal right: andare, venire, arrivare, partire and uscire all answer to it. A teacher or a textbook handed it to you early, you have been applying it ever since, and it has been quietly producing both errors at once.
The question is not whether the verb moves. It is whether the sentence you are building has a direct object in it. A sentence with a direct object takes avere: ho mangiato la pizza, ho letto il libro, ho visto Maria. One exception cuts across that, and it is better met now than later: a reflexive verb takes essere even when an object follows it. Mi sono lavato le mani has a direct object and still takes essere, because the reflexive pronoun settles the auxiliary before the object arrives.
The other direction is not a rule, and pretending otherwise is what breaks. No direct object does not mean essere. It means the sentence has told you nothing yet, and you now need to know which group the verb belongs to. Essere goes with arrival and departure, with change of state, and with the reflexives, and those are the ones you can see coming. Plenty of other verbs take no object and take avere anyway, because what they name is something you do rather than something that happens to you: ho dormito, ho viaggiato, ho camminato, ho parlato. That is where sono viaggiato comes from, and nothing about viaggiare ever pointed at essere.
Ho mangiato una pizza.
Ho viaggiato tutta la notte.
Siamo andati al mare.
Mi sono alzato alle sei.
Mi è sembrato strano.
Notice what the third and fourth sentences do to their endings. With essere the participle follows the subject (andati, alzato), and with avere it stays in -o, unless a direct object pronoun has come first, as in l’ho mangiata, which is a separate rule set out in the post on ho mangiato against ho mangiata. Here the ending is only a symptom: the auxiliary you chose is visible in the last letter of the word after it, so an auxiliary chosen wrongly announces itself twice.
The edge that trips people up
A group of verbs takes both auxiliaries and says something different with each. Ho finito il lavoro is I finished the work, and il film è finito is the film ended. Ho cominciato il libro is I started the book, and il film è cominciato is the film started. Ho passato due giorni a Roma is I spent two days in Rome, and sono passato da casa tua is I dropped by your place. The pattern holds: with a direct object, avere; with no object, where the subject is the thing undergoing the change, essere.
Ho finito il lavoro, e poi il film è finito.
The modals sit on the same fault line, and the rule there is that the modal borrows the auxiliary of the infinitive it governs. Andare takes essere, so sono dovuto andare. Mangiare takes avere, so ho dovuto mangiare. With a non-reflexive infinitive avere is available as well, so ho dovuto andare exists alongside sono dovuto andare, and neither is being ranked here. With a reflexive infinitive the two auxiliaries both exist and the pronoun moves with the choice: mi sono dovuto alzare, with the pronoun in front, and ho dovuto alzarmi, with the pronoun stuck to the infinitive. Both sentences are correct Italian and they say the same thing.
Sono dovuto andare via presto.
How to hear it
Put che cosa? after the verb and see whether your sentence could answer it. Ho letto che cosa? Il libro. The question makes sense, so you are in the avere family, and you stay there on the days you leave the answer out: ho letto tutta la sera. That is the whole of what the test tells you, and it runs in one direction only. A sentence that could answer che cosa? takes avere, unless its verb is reflexive: mi sono lavato le mani answers the question and still takes essere. A sentence that could not has simply finished the test without an answer, and dormire, viaggiare, camminare and parlare all finish it that way and take avere regardless.
So the test settles one side, and the other side is two things to know. The first is the group: arrival, departure, change of state, the reflexives. The second is a short list that takes essere with nothing moving or arriving at all: essere, stare, restare, rimanere, piacere, sembrare, mancare, succedere, costare, durare. La casa è costata troppo, il film è durato tre ore, mi sono rimaste due cose da fare. No test derives this list and no pattern generates it, which is why it is given here as a list rather than as a reason. It is more honest to name a residue than to dress it as a rule.
What the che cosa? test really buys you is the right question at the right moment. You choose the auxiliary before you have said the verb, which is why the wrong one is so hard to catch: by the time the mistake is audible it is two words behind you. Asking what could follow the verb asks it a beat earlier, while the sentence is still yours to build.