There are several methods for making a wandering AI. They differ in both quality and performance. There is no obvious best solution, different methods will suite different games better. For each method I have listed some advantages and disadvantages.
If you are using one of the included movement scripts you can for example change the destination of the AI whenever it has reached the end of its current path:
Ignores the actual distance to the point which means it can produce very long paths if the world is not very open (see the video above).
Has a slight bias towards points close to walls/obstacles as any points that were generated inside the obstacles would have to be snapped to the closest point on the graph.
Misc
Ignores penalties when picking points (penalties will be taken into account when searching for a path to the point though).
Method 2: Random node in the whole graph
Sometimes you just want something very simple. Instead of picking a node around the current position, you can just pick a random node in the graph and try to walk towards the position of that node.
Some other check that might be relevant for your game. If one of these checks fail you can pick a new random node and run the checks again. Unless valid nodes are very rare you will likely find a valid node quickly.
Advantages
Very fast (unless you use the generic approach above)
Simple code Disadvantages
Very little control over the length of the path. Misc
Ignores penalties when picking points (penalties will be taken into account when searching for a path to the point though).
Method 3: The RandomPath type
The RandomPath type is a path type that in contrast to the normal paths which calculate a path from a specific point to another specific point, calculates a random path away from a starting point.
If you are using one of the built-in movement scripts (see Movement scripts) you can do something like this:
// Disable the agent's internal automatic path recalculation
Every node that is considered has the same probability of being chosen, no bias towards being near obstacles like in Method 1: Random point inside a circle.
A minimum path cost can be set (searchLength).
Disadvantages
Can be slow for long paths.
Does not work that well for navmesh/recast graphs as every node has the same probability of being chosen, which will cause a bias towards regions with a lot of detail (and thus more and smaller nodes).
The ConstantPath type is a path type which will find all nodes which can be reached from the start point with a cost at most equal to a particular value. After all those nodes have been found we can pick one or more random points on the surface of those nodes.
Can pick multiple random points with just a single path request.
The probability of chosing a node is proportional to its surface area (so if all nodes have the same size, e.g when using a grid graph then every node that is considered has the same probability of being chosen). There is no bias towards being near obstacles like in Method 1: Random point inside a circle.
Possible to do custom filtering of the nodes afterwards if that should be necessary.
A breadth-first search is a simple search that searches outwards from the starting node a single node at a time. It doesn't take penalties or any other types of costs into account. This means for example that moving diagonally on a grid graph has the same cost as moving along one of the 4 non-diagonal connections.
The probability of chosing a node is proportional to its surface area (so if all nodes have the same size, e.g when using a grid graph then every node that is considered has the same probability of being chosen). There is no bias towards being near obstacles like in Method 1: Random point inside a circle.
Possible to do custom filtering of the nodes afterwards if that should be necessary.
No round trip to the pathfinding system necessary which can save some overhead.
Does not use the pathfinding threads, so you loose the ability to easily offload it from the main Unity thead.
Does not work particularly well for navmesh/recast graphs as the paths will have a large variation in length depending on the detail of the navmesh (more and smaller nodes means the BFS will not reach as far).
Misc
Does not take penalties or any other costs into account, only the number of nodes traversed is relevant.