I recently left Microsoft where we had a lot of automation for a smaller company with just a bit of automation to help begin the process of automating a significant amount of our testing. Fortunately management here had already realized they needed to step up their automation, however even after acknowledging that they needed more automation, actually providing the resources necessary to get that automation up and running has been a bit more difficult.
Because my company had already had some automation successes, and also some automation failures, one of the things that I knew I would need to do is build confidence in our automation both among developers and management as well as other stakeholders. For this reason, I picked a few simple projects with big returns as the first few projects to tackle to show some noticeable increases in productivity and turn around time. The first 2 tools I created actually weren't even necessarily automation. The first was a tool to aid manual testing by inserting data into a log file that would make the data easier to work with when run through our product which parses that log and inserts it into a database. This tool was very simple, but allowed us to do way more in depth testing, increasing our confidence while also speeding up the process. The second was just modifying some of the existing automated tests and adding some tools to use a single mechanism for a) kicking off the automation (mstest) b) logging and reporting results and c) being run build over build. The third one was a tool for automated deployment validation that I outlined in this answer: http://sqa.stackexchange.com/questions/1469/deployment-testingDeployment Testing. In summary, when trying to convince management (and anyone else) that automation can speed up testing and improve your confidence level, it's nice to have some concrete examples, so a couple of quick tools like this that have already added value can be really useful in convincing management to allow you to do more.
The next pieces I plan on tackling are a UI automation framework (an abstraction on top of the current selenium/webdriver build) and then going a level deeper to test at the HTTP and database layers.
I am not familiar with Automation Anywhere, however I do know that the correct suite of automation tools depends largely on what you are testing. Are you only talking about UI automation, or are you talking about other additional automation? What sort of UI is it - web page, windows app, flash, silverlight, etc? What OS's/Browsers/environments will you need to run your automation in? More often than not, the success of your automation will have more to do with your implementation than it does on the underlying framework you are using. An example of a common mistake is using the existing framework out of the box with no abstraction on top of it, often using tools like recorders to record and playback test cases. While this will get you up and going quickly, it will also make maintenance and stability of your automation difficult if not impossible. Take the time to invest in building out a proper abstraction and it will make developing and maintaining your automated tests much simpler.